sched: prioritize non-migratable tasks over migratable ones
[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 static inline struct task_struct *rt_task_of(struct sched_rt_entity *rt_se)
49 {
50         return container_of(rt_se, struct task_struct, rt);
51 }
52
53 static inline int on_rt_rq(struct sched_rt_entity *rt_se)
54 {
55         return !list_empty(&rt_se->run_list);
56 }
57
58 #ifdef CONFIG_RT_GROUP_SCHED
59
60 static inline u64 sched_rt_runtime(struct rt_rq *rt_rq)
61 {
62         if (!rt_rq->tg)
63                 return RUNTIME_INF;
64
65         return rt_rq->rt_runtime;
66 }
67
68 static inline u64 sched_rt_period(struct rt_rq *rt_rq)
69 {
70         return ktime_to_ns(rt_rq->tg->rt_bandwidth.rt_period);
71 }
72
73 #define for_each_leaf_rt_rq(rt_rq, rq) \
74         list_for_each_entry(rt_rq, &rq->leaf_rt_rq_list, leaf_rt_rq_list)
75
76 static inline struct rq *rq_of_rt_rq(struct rt_rq *rt_rq)
77 {
78         return rt_rq->rq;
79 }
80
81 static inline struct rt_rq *rt_rq_of_se(struct sched_rt_entity *rt_se)
82 {
83         return rt_se->rt_rq;
84 }
85
86 #define for_each_sched_rt_entity(rt_se) \
87         for (; rt_se; rt_se = rt_se->parent)
88
89 static inline struct rt_rq *group_rt_rq(struct sched_rt_entity *rt_se)
90 {
91         return rt_se->my_q;
92 }
93
94 static void enqueue_rt_entity(struct sched_rt_entity *rt_se);
95 static void dequeue_rt_entity(struct sched_rt_entity *rt_se);
96
97 static void sched_rt_rq_enqueue(struct rt_rq *rt_rq)
98 {
99         struct sched_rt_entity *rt_se = rt_rq->rt_se;
100
101         if (rt_se && !on_rt_rq(rt_se) && rt_rq->rt_nr_running) {
102                 struct task_struct *curr = rq_of_rt_rq(rt_rq)->curr;
103
104                 enqueue_rt_entity(rt_se);
105                 if (rt_rq->highest_prio < curr->prio)
106                         resched_task(curr);
107         }
108 }
109
110 static void sched_rt_rq_dequeue(struct rt_rq *rt_rq)
111 {
112         struct sched_rt_entity *rt_se = rt_rq->rt_se;
113
114         if (rt_se && on_rt_rq(rt_se))
115                 dequeue_rt_entity(rt_se);
116 }
117
118 static inline int rt_rq_throttled(struct rt_rq *rt_rq)
119 {
120         return rt_rq->rt_throttled && !rt_rq->rt_nr_boosted;
121 }
122
123 static int rt_se_boosted(struct sched_rt_entity *rt_se)
124 {
125         struct rt_rq *rt_rq = group_rt_rq(rt_se);
126         struct task_struct *p;
127
128         if (rt_rq)
129                 return !!rt_rq->rt_nr_boosted;
130
131         p = rt_task_of(rt_se);
132         return p->prio != p->normal_prio;
133 }
134
135 #ifdef CONFIG_SMP
136 static inline cpumask_t sched_rt_period_mask(void)
137 {
138         return cpu_rq(smp_processor_id())->rd->span;
139 }
140 #else
141 static inline cpumask_t sched_rt_period_mask(void)
142 {
143         return cpu_online_map;
144 }
145 #endif
146
147 static inline
148 struct rt_rq *sched_rt_period_rt_rq(struct rt_bandwidth *rt_b, int cpu)
149 {
150         return container_of(rt_b, struct task_group, rt_bandwidth)->rt_rq[cpu];
151 }
152
153 static inline struct rt_bandwidth *sched_rt_bandwidth(struct rt_rq *rt_rq)
154 {
155         return &rt_rq->tg->rt_bandwidth;
156 }
157
158 #else
159
160 static inline u64 sched_rt_runtime(struct rt_rq *rt_rq)
161 {
162         return rt_rq->rt_runtime;
163 }
164
165 static inline u64 sched_rt_period(struct rt_rq *rt_rq)
166 {
167         return ktime_to_ns(def_rt_bandwidth.rt_period);
168 }
169
170 #define for_each_leaf_rt_rq(rt_rq, rq) \
171         for (rt_rq = &rq->rt; rt_rq; rt_rq = NULL)
172
173 static inline struct rq *rq_of_rt_rq(struct rt_rq *rt_rq)
174 {
175         return container_of(rt_rq, struct rq, rt);
176 }
177
178 static inline struct rt_rq *rt_rq_of_se(struct sched_rt_entity *rt_se)
179 {
180         struct task_struct *p = rt_task_of(rt_se);
181         struct rq *rq = task_rq(p);
182
183         return &rq->rt;
184 }
185
186 #define for_each_sched_rt_entity(rt_se) \
187         for (; rt_se; rt_se = NULL)
188
189 static inline struct rt_rq *group_rt_rq(struct sched_rt_entity *rt_se)
190 {
191         return NULL;
192 }
193
194 static inline void sched_rt_rq_enqueue(struct rt_rq *rt_rq)
195 {
196 }
197
198 static inline void sched_rt_rq_dequeue(struct rt_rq *rt_rq)
199 {
200 }
201
202 static inline int rt_rq_throttled(struct rt_rq *rt_rq)
203 {
204         return rt_rq->rt_throttled;
205 }
206
207 static inline cpumask_t sched_rt_period_mask(void)
208 {
209         return cpu_online_map;
210 }
211
212 static inline
213 struct rt_rq *sched_rt_period_rt_rq(struct rt_bandwidth *rt_b, int cpu)
214 {
215         return &cpu_rq(cpu)->rt;
216 }
217
218 static inline struct rt_bandwidth *sched_rt_bandwidth(struct rt_rq *rt_rq)
219 {
220         return &def_rt_bandwidth;
221 }
222
223 #endif
224
225 static int do_sched_rt_period_timer(struct rt_bandwidth *rt_b, int overrun)
226 {
227         int i, idle = 1;
228         cpumask_t span;
229
230         if (rt_b->rt_runtime == RUNTIME_INF)
231                 return 1;
232
233         span = sched_rt_period_mask();
234         for_each_cpu_mask(i, span) {
235                 int enqueue = 0;
236                 struct rt_rq *rt_rq = sched_rt_period_rt_rq(rt_b, i);
237                 struct rq *rq = rq_of_rt_rq(rt_rq);
238
239                 spin_lock(&rq->lock);
240                 if (rt_rq->rt_time) {
241                         u64 runtime;
242
243                         spin_lock(&rt_rq->rt_runtime_lock);
244                         runtime = rt_rq->rt_runtime;
245                         rt_rq->rt_time -= min(rt_rq->rt_time, overrun*runtime);
246                         if (rt_rq->rt_throttled && rt_rq->rt_time < runtime) {
247                                 rt_rq->rt_throttled = 0;
248                                 enqueue = 1;
249                         }
250                         if (rt_rq->rt_time || rt_rq->rt_nr_running)
251                                 idle = 0;
252                         spin_unlock(&rt_rq->rt_runtime_lock);
253                 }
254
255                 if (enqueue)
256                         sched_rt_rq_enqueue(rt_rq);
257                 spin_unlock(&rq->lock);
258         }
259
260         return idle;
261 }
262
263 #ifdef CONFIG_SMP
264 static int balance_runtime(struct rt_rq *rt_rq)
265 {
266         struct rt_bandwidth *rt_b = sched_rt_bandwidth(rt_rq);
267         struct root_domain *rd = cpu_rq(smp_processor_id())->rd;
268         int i, weight, more = 0;
269         u64 rt_period;
270
271         weight = cpus_weight(rd->span);
272
273         spin_lock(&rt_b->rt_runtime_lock);
274         rt_period = ktime_to_ns(rt_b->rt_period);
275         for_each_cpu_mask(i, rd->span) {
276                 struct rt_rq *iter = sched_rt_period_rt_rq(rt_b, i);
277                 s64 diff;
278
279                 if (iter == rt_rq)
280                         continue;
281
282                 spin_lock(&iter->rt_runtime_lock);
283                 diff = iter->rt_runtime - iter->rt_time;
284                 if (diff > 0) {
285                         do_div(diff, weight);
286                         if (rt_rq->rt_runtime + diff > rt_period)
287                                 diff = rt_period - rt_rq->rt_runtime;
288                         iter->rt_runtime -= diff;
289                         rt_rq->rt_runtime += diff;
290                         more = 1;
291                         if (rt_rq->rt_runtime == rt_period) {
292                                 spin_unlock(&iter->rt_runtime_lock);
293                                 break;
294                         }
295                 }
296                 spin_unlock(&iter->rt_runtime_lock);
297         }
298         spin_unlock(&rt_b->rt_runtime_lock);
299
300         return more;
301 }
302 #endif
303
304 static inline int rt_se_prio(struct sched_rt_entity *rt_se)
305 {
306 #ifdef CONFIG_RT_GROUP_SCHED
307         struct rt_rq *rt_rq = group_rt_rq(rt_se);
308
309         if (rt_rq)
310                 return rt_rq->highest_prio;
311 #endif
312
313         return rt_task_of(rt_se)->prio;
314 }
315
316 static int sched_rt_runtime_exceeded(struct rt_rq *rt_rq)
317 {
318         u64 runtime = sched_rt_runtime(rt_rq);
319
320         if (runtime == RUNTIME_INF)
321                 return 0;
322
323         if (rt_rq->rt_throttled)
324                 return rt_rq_throttled(rt_rq);
325
326         if (sched_rt_runtime(rt_rq) >= sched_rt_period(rt_rq))
327                 return 0;
328
329 #ifdef CONFIG_SMP
330         if (rt_rq->rt_time > runtime) {
331                 int more;
332
333                 spin_unlock(&rt_rq->rt_runtime_lock);
334                 more = balance_runtime(rt_rq);
335                 spin_lock(&rt_rq->rt_runtime_lock);
336
337                 if (more)
338                         runtime = sched_rt_runtime(rt_rq);
339         }
340 #endif
341
342         if (rt_rq->rt_time > runtime) {
343                 rt_rq->rt_throttled = 1;
344                 if (rt_rq_throttled(rt_rq)) {
345                         sched_rt_rq_dequeue(rt_rq);
346                         return 1;
347                 }
348         }
349
350         return 0;
351 }
352
353 /*
354  * Update the current task's runtime statistics. Skip current tasks that
355  * are not in our scheduling class.
356  */
357 static void update_curr_rt(struct rq *rq)
358 {
359         struct task_struct *curr = rq->curr;
360         struct sched_rt_entity *rt_se = &curr->rt;
361         struct rt_rq *rt_rq = rt_rq_of_se(rt_se);
362         u64 delta_exec;
363
364         if (!task_has_rt_policy(curr))
365                 return;
366
367         delta_exec = rq->clock - curr->se.exec_start;
368         if (unlikely((s64)delta_exec < 0))
369                 delta_exec = 0;
370
371         schedstat_set(curr->se.exec_max, max(curr->se.exec_max, delta_exec));
372
373         curr->se.sum_exec_runtime += delta_exec;
374         curr->se.exec_start = rq->clock;
375         cpuacct_charge(curr, delta_exec);
376
377         for_each_sched_rt_entity(rt_se) {
378                 rt_rq = rt_rq_of_se(rt_se);
379
380                 spin_lock(&rt_rq->rt_runtime_lock);
381                 rt_rq->rt_time += delta_exec;
382                 if (sched_rt_runtime_exceeded(rt_rq))
383                         resched_task(curr);
384                 spin_unlock(&rt_rq->rt_runtime_lock);
385         }
386 }
387
388 static inline
389 void inc_rt_tasks(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
390 {
391         WARN_ON(!rt_prio(rt_se_prio(rt_se)));
392         rt_rq->rt_nr_running++;
393 #if defined CONFIG_SMP || defined CONFIG_RT_GROUP_SCHED
394         if (rt_se_prio(rt_se) < rt_rq->highest_prio)
395                 rt_rq->highest_prio = rt_se_prio(rt_se);
396 #endif
397 #ifdef CONFIG_SMP
398         if (rt_se->nr_cpus_allowed > 1) {
399                 struct rq *rq = rq_of_rt_rq(rt_rq);
400                 rq->rt.rt_nr_migratory++;
401         }
402
403         update_rt_migration(rq_of_rt_rq(rt_rq));
404 #endif
405 #ifdef CONFIG_RT_GROUP_SCHED
406         if (rt_se_boosted(rt_se))
407                 rt_rq->rt_nr_boosted++;
408
409         if (rt_rq->tg)
410                 start_rt_bandwidth(&rt_rq->tg->rt_bandwidth);
411 #else
412         start_rt_bandwidth(&def_rt_bandwidth);
413 #endif
414 }
415
416 static inline
417 void dec_rt_tasks(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
418 {
419         WARN_ON(!rt_prio(rt_se_prio(rt_se)));
420         WARN_ON(!rt_rq->rt_nr_running);
421         rt_rq->rt_nr_running--;
422 #if defined CONFIG_SMP || defined CONFIG_RT_GROUP_SCHED
423         if (rt_rq->rt_nr_running) {
424                 struct rt_prio_array *array;
425
426                 WARN_ON(rt_se_prio(rt_se) < rt_rq->highest_prio);
427                 if (rt_se_prio(rt_se) == rt_rq->highest_prio) {
428                         /* recalculate */
429                         array = &rt_rq->active;
430                         rt_rq->highest_prio =
431                                 sched_find_first_bit(array->bitmap);
432                 } /* otherwise leave rq->highest prio alone */
433         } else
434                 rt_rq->highest_prio = MAX_RT_PRIO;
435 #endif
436 #ifdef CONFIG_SMP
437         if (rt_se->nr_cpus_allowed > 1) {
438                 struct rq *rq = rq_of_rt_rq(rt_rq);
439                 rq->rt.rt_nr_migratory--;
440         }
441
442         update_rt_migration(rq_of_rt_rq(rt_rq));
443 #endif /* CONFIG_SMP */
444 #ifdef CONFIG_RT_GROUP_SCHED
445         if (rt_se_boosted(rt_se))
446                 rt_rq->rt_nr_boosted--;
447
448         WARN_ON(!rt_rq->rt_nr_running && rt_rq->rt_nr_boosted);
449 #endif
450 }
451
452 static void enqueue_rt_entity(struct sched_rt_entity *rt_se)
453 {
454         struct rt_rq *rt_rq = rt_rq_of_se(rt_se);
455         struct rt_prio_array *array = &rt_rq->active;
456         struct rt_rq *group_rq = group_rt_rq(rt_se);
457
458         if (group_rq && rt_rq_throttled(group_rq))
459                 return;
460
461         if (rt_se->nr_cpus_allowed == 1)
462                 list_add_tail(&rt_se->run_list,
463                               array->xqueue + rt_se_prio(rt_se));
464         else
465                 list_add_tail(&rt_se->run_list,
466                               array->squeue + rt_se_prio(rt_se));
467
468         __set_bit(rt_se_prio(rt_se), array->bitmap);
469
470         inc_rt_tasks(rt_se, rt_rq);
471 }
472
473 static void dequeue_rt_entity(struct sched_rt_entity *rt_se)
474 {
475         struct rt_rq *rt_rq = rt_rq_of_se(rt_se);
476         struct rt_prio_array *array = &rt_rq->active;
477
478         list_del_init(&rt_se->run_list);
479         if (list_empty(array->squeue + rt_se_prio(rt_se))
480             && list_empty(array->xqueue + rt_se_prio(rt_se)))
481                 __clear_bit(rt_se_prio(rt_se), array->bitmap);
482
483         dec_rt_tasks(rt_se, rt_rq);
484 }
485
486 /*
487  * Because the prio of an upper entry depends on the lower
488  * entries, we must remove entries top - down.
489  */
490 static void dequeue_rt_stack(struct task_struct *p)
491 {
492         struct sched_rt_entity *rt_se, *back = NULL;
493
494         rt_se = &p->rt;
495         for_each_sched_rt_entity(rt_se) {
496                 rt_se->back = back;
497                 back = rt_se;
498         }
499
500         for (rt_se = back; rt_se; rt_se = rt_se->back) {
501                 if (on_rt_rq(rt_se))
502                         dequeue_rt_entity(rt_se);
503         }
504 }
505
506 /*
507  * Adding/removing a task to/from a priority array:
508  */
509 static void enqueue_task_rt(struct rq *rq, struct task_struct *p, int wakeup)
510 {
511         struct sched_rt_entity *rt_se = &p->rt;
512
513         if (wakeup)
514                 rt_se->timeout = 0;
515
516         dequeue_rt_stack(p);
517
518         /*
519          * enqueue everybody, bottom - up.
520          */
521         for_each_sched_rt_entity(rt_se)
522                 enqueue_rt_entity(rt_se);
523 }
524
525 static void dequeue_task_rt(struct rq *rq, struct task_struct *p, int sleep)
526 {
527         struct sched_rt_entity *rt_se = &p->rt;
528         struct rt_rq *rt_rq;
529
530         update_curr_rt(rq);
531
532         dequeue_rt_stack(p);
533
534         /*
535          * re-enqueue all non-empty rt_rq entities.
536          */
537         for_each_sched_rt_entity(rt_se) {
538                 rt_rq = group_rt_rq(rt_se);
539                 if (rt_rq && rt_rq->rt_nr_running)
540                         enqueue_rt_entity(rt_se);
541         }
542 }
543
544 /*
545  * Put task to the end of the run list without the overhead of dequeue
546  * followed by enqueue.
547  *
548  * Note: We always enqueue the task to the shared-queue, regardless of its
549  * previous position w.r.t. exclusive vs shared.  This is so that exclusive RR
550  * tasks fairly round-robin with all tasks on the runqueue, not just other
551  * exclusive tasks.
552  */
553 static
554 void requeue_rt_entity(struct rt_rq *rt_rq, struct sched_rt_entity *rt_se)
555 {
556         struct rt_prio_array *array = &rt_rq->active;
557
558         list_del_init(&rt_se->run_list);
559         list_add_tail(&rt_se->run_list, array->squeue + rt_se_prio(rt_se));
560 }
561
562 static void requeue_task_rt(struct rq *rq, struct task_struct *p)
563 {
564         struct sched_rt_entity *rt_se = &p->rt;
565         struct rt_rq *rt_rq;
566
567         for_each_sched_rt_entity(rt_se) {
568                 rt_rq = rt_rq_of_se(rt_se);
569                 requeue_rt_entity(rt_rq, rt_se);
570         }
571 }
572
573 static void yield_task_rt(struct rq *rq)
574 {
575         requeue_task_rt(rq, rq->curr);
576 }
577
578 #ifdef CONFIG_SMP
579 static int find_lowest_rq(struct task_struct *task);
580
581 static int select_task_rq_rt(struct task_struct *p, int sync)
582 {
583         struct rq *rq = task_rq(p);
584
585         /*
586          * If the current task is an RT task, then
587          * try to see if we can wake this RT task up on another
588          * runqueue. Otherwise simply start this RT task
589          * on its current runqueue.
590          *
591          * We want to avoid overloading runqueues. Even if
592          * the RT task is of higher priority than the current RT task.
593          * RT tasks behave differently than other tasks. If
594          * one gets preempted, we try to push it off to another queue.
595          * So trying to keep a preempting RT task on the same
596          * cache hot CPU will force the running RT task to
597          * a cold CPU. So we waste all the cache for the lower
598          * RT task in hopes of saving some of a RT task
599          * that is just being woken and probably will have
600          * cold cache anyway.
601          */
602         if (unlikely(rt_task(rq->curr)) &&
603             (p->rt.nr_cpus_allowed > 1)) {
604                 int cpu = find_lowest_rq(p);
605
606                 return (cpu == -1) ? task_cpu(p) : cpu;
607         }
608
609         /*
610          * Otherwise, just let it ride on the affined RQ and the
611          * post-schedule router will push the preempted task away
612          */
613         return task_cpu(p);
614 }
615 #endif /* CONFIG_SMP */
616
617 static struct sched_rt_entity *pick_next_rt_entity(struct rq *rq,
618                                                    struct rt_rq *rt_rq);
619
620 /*
621  * Preempt the current task with a newly woken task if needed:
622  */
623 static void check_preempt_curr_rt(struct rq *rq, struct task_struct *p)
624 {
625         if (p->prio < rq->curr->prio) {
626                 resched_task(rq->curr);
627                 return;
628         }
629
630 #ifdef CONFIG_SMP
631         /*
632          * If:
633          *
634          * - the newly woken task is of equal priority to the current task
635          * - the newly woken task is non-migratable while current is migratable
636          * - current will be preempted on the next reschedule
637          *
638          * we should check to see if current can readily move to a different
639          * cpu.  If so, we will reschedule to allow the push logic to try
640          * to move current somewhere else, making room for our non-migratable
641          * task.
642          */
643         if((p->prio == rq->curr->prio)
644            && p->rt.nr_cpus_allowed == 1
645            && rq->curr->rt.nr_cpus_allowed != 1
646            && pick_next_rt_entity(rq, &rq->rt) != &rq->curr->rt) {
647                 cpumask_t mask;
648
649                 if (cpupri_find(&rq->rd->cpupri, rq->curr, &mask))
650                         /*
651                          * There appears to be other cpus that can accept
652                          * current, so lets reschedule to try and push it away
653                          */
654                         resched_task(rq->curr);
655         }
656 #endif
657 }
658
659 static struct sched_rt_entity *pick_next_rt_entity(struct rq *rq,
660                                                    struct rt_rq *rt_rq)
661 {
662         struct rt_prio_array *array = &rt_rq->active;
663         struct sched_rt_entity *next = NULL;
664         struct list_head *queue;
665         int idx;
666
667         idx = sched_find_first_bit(array->bitmap);
668         BUG_ON(idx >= MAX_RT_PRIO);
669
670         queue = array->xqueue + idx;
671         if (!list_empty(queue))
672                 next = list_entry(queue->next, struct sched_rt_entity,
673                                   run_list);
674         else {
675                 queue = array->squeue + idx;
676                 next = list_entry(queue->next, struct sched_rt_entity,
677                                   run_list);
678         }
679
680         return next;
681 }
682
683 static struct task_struct *pick_next_task_rt(struct rq *rq)
684 {
685         struct sched_rt_entity *rt_se;
686         struct task_struct *p;
687         struct rt_rq *rt_rq;
688
689         rt_rq = &rq->rt;
690
691         if (unlikely(!rt_rq->rt_nr_running))
692                 return NULL;
693
694         if (rt_rq_throttled(rt_rq))
695                 return NULL;
696
697         do {
698                 rt_se = pick_next_rt_entity(rq, rt_rq);
699                 BUG_ON(!rt_se);
700                 rt_rq = group_rt_rq(rt_se);
701         } while (rt_rq);
702
703         p = rt_task_of(rt_se);
704         p->se.exec_start = rq->clock;
705         return p;
706 }
707
708 static void put_prev_task_rt(struct rq *rq, struct task_struct *p)
709 {
710         update_curr_rt(rq);
711         p->se.exec_start = 0;
712 }
713
714 #ifdef CONFIG_SMP
715
716 /* Only try algorithms three times */
717 #define RT_MAX_TRIES 3
718
719 static int double_lock_balance(struct rq *this_rq, struct rq *busiest);
720 static void deactivate_task(struct rq *rq, struct task_struct *p, int sleep);
721
722 static int pick_rt_task(struct rq *rq, struct task_struct *p, int cpu)
723 {
724         if (!task_running(rq, p) &&
725             (cpu < 0 || cpu_isset(cpu, p->cpus_allowed)) &&
726             (p->rt.nr_cpus_allowed > 1))
727                 return 1;
728         return 0;
729 }
730
731 /* Return the second highest RT task, NULL otherwise */
732 static struct task_struct *pick_next_highest_task_rt(struct rq *rq, int cpu)
733 {
734         struct task_struct *next = NULL;
735         struct sched_rt_entity *rt_se;
736         struct rt_prio_array *array;
737         struct rt_rq *rt_rq;
738         int idx;
739
740         for_each_leaf_rt_rq(rt_rq, rq) {
741                 array = &rt_rq->active;
742                 idx = sched_find_first_bit(array->bitmap);
743  next_idx:
744                 if (idx >= MAX_RT_PRIO)
745                         continue;
746                 if (next && next->prio < idx)
747                         continue;
748                 list_for_each_entry(rt_se, array->squeue + idx, run_list) {
749                         struct task_struct *p = rt_task_of(rt_se);
750                         if (pick_rt_task(rq, p, cpu)) {
751                                 next = p;
752                                 break;
753                         }
754                 }
755                 if (!next) {
756                         idx = find_next_bit(array->bitmap, MAX_RT_PRIO, idx+1);
757                         goto next_idx;
758                 }
759         }
760
761         return next;
762 }
763
764 static DEFINE_PER_CPU(cpumask_t, local_cpu_mask);
765
766 static int find_lowest_cpus(struct task_struct *task, cpumask_t *lowest_mask)
767 {
768         int       lowest_prio = -1;
769         int       lowest_cpu  = -1;
770         int       count       = 0;
771         int       cpu;
772
773         cpus_and(*lowest_mask, task_rq(task)->rd->online, task->cpus_allowed);
774
775         /*
776          * Scan each rq for the lowest prio.
777          */
778         for_each_cpu_mask(cpu, *lowest_mask) {
779                 struct rq *rq = cpu_rq(cpu);
780
781                 /* We look for lowest RT prio or non-rt CPU */
782                 if (rq->rt.highest_prio >= MAX_RT_PRIO) {
783                         /*
784                          * if we already found a low RT queue
785                          * and now we found this non-rt queue
786                          * clear the mask and set our bit.
787                          * Otherwise just return the queue as is
788                          * and the count==1 will cause the algorithm
789                          * to use the first bit found.
790                          */
791                         if (lowest_cpu != -1) {
792                                 cpus_clear(*lowest_mask);
793                                 cpu_set(rq->cpu, *lowest_mask);
794                         }
795                         return 1;
796                 }
797
798                 /* no locking for now */
799                 if ((rq->rt.highest_prio > task->prio)
800                     && (rq->rt.highest_prio >= lowest_prio)) {
801                         if (rq->rt.highest_prio > lowest_prio) {
802                                 /* new low - clear old data */
803                                 lowest_prio = rq->rt.highest_prio;
804                                 lowest_cpu = cpu;
805                                 count = 0;
806                         }
807                         count++;
808                 } else
809                         cpu_clear(cpu, *lowest_mask);
810         }
811
812         /*
813          * Clear out all the set bits that represent
814          * runqueues that were of higher prio than
815          * the lowest_prio.
816          */
817         if (lowest_cpu > 0) {
818                 /*
819                  * Perhaps we could add another cpumask op to
820                  * zero out bits. Like cpu_zero_bits(cpumask, nrbits);
821                  * Then that could be optimized to use memset and such.
822                  */
823                 for_each_cpu_mask(cpu, *lowest_mask) {
824                         if (cpu >= lowest_cpu)
825                                 break;
826                         cpu_clear(cpu, *lowest_mask);
827                 }
828         }
829
830         return count;
831 }
832
833 static inline int pick_optimal_cpu(int this_cpu, cpumask_t *mask)
834 {
835         int first;
836
837         /* "this_cpu" is cheaper to preempt than a remote processor */
838         if ((this_cpu != -1) && cpu_isset(this_cpu, *mask))
839                 return this_cpu;
840
841         first = first_cpu(*mask);
842         if (first != NR_CPUS)
843                 return first;
844
845         return -1;
846 }
847
848 static int find_lowest_rq(struct task_struct *task)
849 {
850         struct sched_domain *sd;
851         cpumask_t *lowest_mask = &__get_cpu_var(local_cpu_mask);
852         int this_cpu = smp_processor_id();
853         int cpu      = task_cpu(task);
854         int count    = find_lowest_cpus(task, lowest_mask);
855
856         if (!count)
857                 return -1; /* No targets found */
858
859         /*
860          * There is no sense in performing an optimal search if only one
861          * target is found.
862          */
863         if (count == 1)
864                 return first_cpu(*lowest_mask);
865
866         /*
867          * At this point we have built a mask of cpus representing the
868          * lowest priority tasks in the system.  Now we want to elect
869          * the best one based on our affinity and topology.
870          *
871          * We prioritize the last cpu that the task executed on since
872          * it is most likely cache-hot in that location.
873          */
874         if (cpu_isset(cpu, *lowest_mask))
875                 return cpu;
876
877         /*
878          * Otherwise, we consult the sched_domains span maps to figure
879          * out which cpu is logically closest to our hot cache data.
880          */
881         if (this_cpu == cpu)
882                 this_cpu = -1; /* Skip this_cpu opt if the same */
883
884         for_each_domain(cpu, sd) {
885                 if (sd->flags & SD_WAKE_AFFINE) {
886                         cpumask_t domain_mask;
887                         int       best_cpu;
888
889                         cpus_and(domain_mask, sd->span, *lowest_mask);
890
891                         best_cpu = pick_optimal_cpu(this_cpu,
892                                                     &domain_mask);
893                         if (best_cpu != -1)
894                                 return best_cpu;
895                 }
896         }
897
898         /*
899          * And finally, if there were no matches within the domains
900          * just give the caller *something* to work with from the compatible
901          * locations.
902          */
903         return pick_optimal_cpu(this_cpu, lowest_mask);
904 }
905
906 /* Will lock the rq it finds */
907 static struct rq *find_lock_lowest_rq(struct task_struct *task, struct rq *rq)
908 {
909         struct rq *lowest_rq = NULL;
910         int tries;
911         int cpu;
912
913         for (tries = 0; tries < RT_MAX_TRIES; tries++) {
914                 cpu = find_lowest_rq(task);
915
916                 if ((cpu == -1) || (cpu == rq->cpu))
917                         break;
918
919                 lowest_rq = cpu_rq(cpu);
920
921                 /* if the prio of this runqueue changed, try again */
922                 if (double_lock_balance(rq, lowest_rq)) {
923                         /*
924                          * We had to unlock the run queue. In
925                          * the mean time, task could have
926                          * migrated already or had its affinity changed.
927                          * Also make sure that it wasn't scheduled on its rq.
928                          */
929                         if (unlikely(task_rq(task) != rq ||
930                                      !cpu_isset(lowest_rq->cpu,
931                                                 task->cpus_allowed) ||
932                                      task_running(rq, task) ||
933                                      !task->se.on_rq)) {
934
935                                 spin_unlock(&lowest_rq->lock);
936                                 lowest_rq = NULL;
937                                 break;
938                         }
939                 }
940
941                 /* If this rq is still suitable use it. */
942                 if (lowest_rq->rt.highest_prio > task->prio)
943                         break;
944
945                 /* try again */
946                 spin_unlock(&lowest_rq->lock);
947                 lowest_rq = NULL;
948         }
949
950         return lowest_rq;
951 }
952
953 /*
954  * If the current CPU has more than one RT task, see if the non
955  * running task can migrate over to a CPU that is running a task
956  * of lesser priority.
957  */
958 static int push_rt_task(struct rq *rq)
959 {
960         struct task_struct *next_task;
961         struct rq *lowest_rq;
962         int ret = 0;
963         int paranoid = RT_MAX_TRIES;
964
965         if (!rq->rt.overloaded)
966                 return 0;
967
968         next_task = pick_next_highest_task_rt(rq, -1);
969         if (!next_task)
970                 return 0;
971
972  retry:
973         if (unlikely(next_task == rq->curr)) {
974                 WARN_ON(1);
975                 return 0;
976         }
977
978         /*
979          * It's possible that the next_task slipped in of
980          * higher priority than current. If that's the case
981          * just reschedule current.
982          */
983         if (unlikely(next_task->prio < rq->curr->prio)) {
984                 resched_task(rq->curr);
985                 return 0;
986         }
987
988         /* We might release rq lock */
989         get_task_struct(next_task);
990
991         /* find_lock_lowest_rq locks the rq if found */
992         lowest_rq = find_lock_lowest_rq(next_task, rq);
993         if (!lowest_rq) {
994                 struct task_struct *task;
995                 /*
996                  * find lock_lowest_rq releases rq->lock
997                  * so it is possible that next_task has changed.
998                  * If it has, then try again.
999                  */
1000                 task = pick_next_highest_task_rt(rq, -1);
1001                 if (unlikely(task != next_task) && task && paranoid--) {
1002                         put_task_struct(next_task);
1003                         next_task = task;
1004                         goto retry;
1005                 }
1006                 goto out;
1007         }
1008
1009         deactivate_task(rq, next_task, 0);
1010         set_task_cpu(next_task, lowest_rq->cpu);
1011         activate_task(lowest_rq, next_task, 0);
1012
1013         resched_task(lowest_rq->curr);
1014
1015         spin_unlock(&lowest_rq->lock);
1016
1017         ret = 1;
1018 out:
1019         put_task_struct(next_task);
1020
1021         return ret;
1022 }
1023
1024 /*
1025  * TODO: Currently we just use the second highest prio task on
1026  *       the queue, and stop when it can't migrate (or there's
1027  *       no more RT tasks).  There may be a case where a lower
1028  *       priority RT task has a different affinity than the
1029  *       higher RT task. In this case the lower RT task could
1030  *       possibly be able to migrate where as the higher priority
1031  *       RT task could not.  We currently ignore this issue.
1032  *       Enhancements are welcome!
1033  */
1034 static void push_rt_tasks(struct rq *rq)
1035 {
1036         /* push_rt_task will return true if it moved an RT */
1037         while (push_rt_task(rq))
1038                 ;
1039 }
1040
1041 static int pull_rt_task(struct rq *this_rq)
1042 {
1043         int this_cpu = this_rq->cpu, ret = 0, cpu;
1044         struct task_struct *p, *next;
1045         struct rq *src_rq;
1046
1047         if (likely(!rt_overloaded(this_rq)))
1048                 return 0;
1049
1050         next = pick_next_task_rt(this_rq);
1051
1052         for_each_cpu_mask(cpu, this_rq->rd->rto_mask) {
1053                 if (this_cpu == cpu)
1054                         continue;
1055
1056                 src_rq = cpu_rq(cpu);
1057                 /*
1058                  * We can potentially drop this_rq's lock in
1059                  * double_lock_balance, and another CPU could
1060                  * steal our next task - hence we must cause
1061                  * the caller to recalculate the next task
1062                  * in that case:
1063                  */
1064                 if (double_lock_balance(this_rq, src_rq)) {
1065                         struct task_struct *old_next = next;
1066
1067                         next = pick_next_task_rt(this_rq);
1068                         if (next != old_next)
1069                                 ret = 1;
1070                 }
1071
1072                 /*
1073                  * Are there still pullable RT tasks?
1074                  */
1075                 if (src_rq->rt.rt_nr_running <= 1)
1076                         goto skip;
1077
1078                 p = pick_next_highest_task_rt(src_rq, this_cpu);
1079
1080                 /*
1081                  * Do we have an RT task that preempts
1082                  * the to-be-scheduled task?
1083                  */
1084                 if (p && (!next || (p->prio < next->prio))) {
1085                         WARN_ON(p == src_rq->curr);
1086                         WARN_ON(!p->se.on_rq);
1087
1088                         /*
1089                          * There's a chance that p is higher in priority
1090                          * than what's currently running on its cpu.
1091                          * This is just that p is wakeing up and hasn't
1092                          * had a chance to schedule. We only pull
1093                          * p if it is lower in priority than the
1094                          * current task on the run queue or
1095                          * this_rq next task is lower in prio than
1096                          * the current task on that rq.
1097                          */
1098                         if (p->prio < src_rq->curr->prio ||
1099                             (next && next->prio < src_rq->curr->prio))
1100                                 goto skip;
1101
1102                         ret = 1;
1103
1104                         deactivate_task(src_rq, p, 0);
1105                         set_task_cpu(p, this_cpu);
1106                         activate_task(this_rq, p, 0);
1107                         /*
1108                          * We continue with the search, just in
1109                          * case there's an even higher prio task
1110                          * in another runqueue. (low likelyhood
1111                          * but possible)
1112                          *
1113                          * Update next so that we won't pick a task
1114                          * on another cpu with a priority lower (or equal)
1115                          * than the one we just picked.
1116                          */
1117                         next = p;
1118
1119                 }
1120  skip:
1121                 spin_unlock(&src_rq->lock);
1122         }
1123
1124         return ret;
1125 }
1126
1127 static void pre_schedule_rt(struct rq *rq, struct task_struct *prev)
1128 {
1129         /* Try to pull RT tasks here if we lower this rq's prio */
1130         if (unlikely(rt_task(prev)) && rq->rt.highest_prio > prev->prio)
1131                 pull_rt_task(rq);
1132 }
1133
1134 static void post_schedule_rt(struct rq *rq)
1135 {
1136         /*
1137          * If we have more than one rt_task queued, then
1138          * see if we can push the other rt_tasks off to other CPUS.
1139          * Note we may release the rq lock, and since
1140          * the lock was owned by prev, we need to release it
1141          * first via finish_lock_switch and then reaquire it here.
1142          */
1143         if (unlikely(rq->rt.overloaded)) {
1144                 spin_lock_irq(&rq->lock);
1145                 push_rt_tasks(rq);
1146                 spin_unlock_irq(&rq->lock);
1147         }
1148 }
1149
1150 /*
1151  * If we are not running and we are not going to reschedule soon, we should
1152  * try to push tasks away now
1153  */
1154 static void task_wake_up_rt(struct rq *rq, struct task_struct *p)
1155 {
1156         if (!task_running(rq, p) &&
1157             !test_tsk_need_resched(rq->curr) &&
1158             rq->rt.overloaded)
1159                 push_rt_tasks(rq);
1160 }
1161
1162 static unsigned long
1163 load_balance_rt(struct rq *this_rq, int this_cpu, struct rq *busiest,
1164                 unsigned long max_load_move,
1165                 struct sched_domain *sd, enum cpu_idle_type idle,
1166                 int *all_pinned, int *this_best_prio)
1167 {
1168         /* don't touch RT tasks */
1169         return 0;
1170 }
1171
1172 static int
1173 move_one_task_rt(struct rq *this_rq, int this_cpu, struct rq *busiest,
1174                  struct sched_domain *sd, enum cpu_idle_type idle)
1175 {
1176         /* don't touch RT tasks */
1177         return 0;
1178 }
1179
1180 static void set_cpus_allowed_rt(struct task_struct *p,
1181                                 const cpumask_t *new_mask)
1182 {
1183         int weight = cpus_weight(*new_mask);
1184
1185         BUG_ON(!rt_task(p));
1186
1187         /*
1188          * Update the migration status of the RQ if we have an RT task
1189          * which is running AND changing its weight value.
1190          */
1191         if (p->se.on_rq && (weight != p->rt.nr_cpus_allowed)) {
1192                 struct rq *rq = task_rq(p);
1193
1194                 if ((p->rt.nr_cpus_allowed <= 1) && (weight > 1)) {
1195                         rq->rt.rt_nr_migratory++;
1196                 } else if ((p->rt.nr_cpus_allowed > 1) && (weight <= 1)) {
1197                         BUG_ON(!rq->rt.rt_nr_migratory);
1198                         rq->rt.rt_nr_migratory--;
1199                 }
1200
1201                 update_rt_migration(rq);
1202
1203                 if (unlikely(weight == 1 || p->rt.nr_cpus_allowed == 1))
1204                         /*
1205                          * If either the new or old weight is a "1", we need
1206                          * to requeue to properly move between shared and
1207                          * exclusive queues.
1208                          */
1209                         requeue_task_rt(rq, p);
1210         }
1211
1212         p->cpus_allowed    = *new_mask;
1213         p->rt.nr_cpus_allowed = weight;
1214 }
1215
1216 /* Assumes rq->lock is held */
1217 static void join_domain_rt(struct rq *rq)
1218 {
1219         if (rq->rt.overloaded)
1220                 rt_set_overload(rq);
1221 }
1222
1223 /* Assumes rq->lock is held */
1224 static void leave_domain_rt(struct rq *rq)
1225 {
1226         if (rq->rt.overloaded)
1227                 rt_clear_overload(rq);
1228 }
1229
1230 /*
1231  * When switch from the rt queue, we bring ourselves to a position
1232  * that we might want to pull RT tasks from other runqueues.
1233  */
1234 static void switched_from_rt(struct rq *rq, struct task_struct *p,
1235                            int running)
1236 {
1237         /*
1238          * If there are other RT tasks then we will reschedule
1239          * and the scheduling of the other RT tasks will handle
1240          * the balancing. But if we are the last RT task
1241          * we may need to handle the pulling of RT tasks
1242          * now.
1243          */
1244         if (!rq->rt.rt_nr_running)
1245                 pull_rt_task(rq);
1246 }
1247 #endif /* CONFIG_SMP */
1248
1249 /*
1250  * When switching a task to RT, we may overload the runqueue
1251  * with RT tasks. In this case we try to push them off to
1252  * other runqueues.
1253  */
1254 static void switched_to_rt(struct rq *rq, struct task_struct *p,
1255                            int running)
1256 {
1257         int check_resched = 1;
1258
1259         /*
1260          * If we are already running, then there's nothing
1261          * that needs to be done. But if we are not running
1262          * we may need to preempt the current running task.
1263          * If that current running task is also an RT task
1264          * then see if we can move to another run queue.
1265          */
1266         if (!running) {
1267 #ifdef CONFIG_SMP
1268                 if (rq->rt.overloaded && push_rt_task(rq) &&
1269                     /* Don't resched if we changed runqueues */
1270                     rq != task_rq(p))
1271                         check_resched = 0;
1272 #endif /* CONFIG_SMP */
1273                 if (check_resched && p->prio < rq->curr->prio)
1274                         resched_task(rq->curr);
1275         }
1276 }
1277
1278 /*
1279  * Priority of the task has changed. This may cause
1280  * us to initiate a push or pull.
1281  */
1282 static void prio_changed_rt(struct rq *rq, struct task_struct *p,
1283                             int oldprio, int running)
1284 {
1285         if (running) {
1286 #ifdef CONFIG_SMP
1287                 /*
1288                  * If our priority decreases while running, we
1289                  * may need to pull tasks to this runqueue.
1290                  */
1291                 if (oldprio < p->prio)
1292                         pull_rt_task(rq);
1293                 /*
1294                  * If there's a higher priority task waiting to run
1295                  * then reschedule. Note, the above pull_rt_task
1296                  * can release the rq lock and p could migrate.
1297                  * Only reschedule if p is still on the same runqueue.
1298                  */
1299                 if (p->prio > rq->rt.highest_prio && rq->curr == p)
1300                         resched_task(p);
1301 #else
1302                 /* For UP simply resched on drop of prio */
1303                 if (oldprio < p->prio)
1304                         resched_task(p);
1305 #endif /* CONFIG_SMP */
1306         } else {
1307                 /*
1308                  * This task is not running, but if it is
1309                  * greater than the current running task
1310                  * then reschedule.
1311                  */
1312                 if (p->prio < rq->curr->prio)
1313                         resched_task(rq->curr);
1314         }
1315 }
1316
1317 static void watchdog(struct rq *rq, struct task_struct *p)
1318 {
1319         unsigned long soft, hard;
1320
1321         if (!p->signal)
1322                 return;
1323
1324         soft = p->signal->rlim[RLIMIT_RTTIME].rlim_cur;
1325         hard = p->signal->rlim[RLIMIT_RTTIME].rlim_max;
1326
1327         if (soft != RLIM_INFINITY) {
1328                 unsigned long next;
1329
1330                 p->rt.timeout++;
1331                 next = DIV_ROUND_UP(min(soft, hard), USEC_PER_SEC/HZ);
1332                 if (p->rt.timeout > next)
1333                         p->it_sched_expires = p->se.sum_exec_runtime;
1334         }
1335 }
1336
1337 static void task_tick_rt(struct rq *rq, struct task_struct *p, int queued)
1338 {
1339         update_curr_rt(rq);
1340
1341         watchdog(rq, p);
1342
1343         /*
1344          * RR tasks need a special form of timeslice management.
1345          * FIFO tasks have no timeslices.
1346          */
1347         if (p->policy != SCHED_RR)
1348                 return;
1349
1350         if (--p->rt.time_slice)
1351                 return;
1352
1353         p->rt.time_slice = DEF_TIMESLICE;
1354
1355         /*
1356          * Requeue to the end of queue if we are not the only element
1357          * on the queue:
1358          */
1359         if (p->rt.run_list.prev != p->rt.run_list.next) {
1360                 requeue_task_rt(rq, p);
1361                 set_tsk_need_resched(p);
1362         }
1363 }
1364
1365 static void set_curr_task_rt(struct rq *rq)
1366 {
1367         struct task_struct *p = rq->curr;
1368
1369         p->se.exec_start = rq->clock;
1370 }
1371
1372 static const struct sched_class rt_sched_class = {
1373         .next                   = &fair_sched_class,
1374         .enqueue_task           = enqueue_task_rt,
1375         .dequeue_task           = dequeue_task_rt,
1376         .yield_task             = yield_task_rt,
1377 #ifdef CONFIG_SMP
1378         .select_task_rq         = select_task_rq_rt,
1379 #endif /* CONFIG_SMP */
1380
1381         .check_preempt_curr     = check_preempt_curr_rt,
1382
1383         .pick_next_task         = pick_next_task_rt,
1384         .put_prev_task          = put_prev_task_rt,
1385
1386 #ifdef CONFIG_SMP
1387         .load_balance           = load_balance_rt,
1388         .move_one_task          = move_one_task_rt,
1389         .set_cpus_allowed       = set_cpus_allowed_rt,
1390         .join_domain            = join_domain_rt,
1391         .leave_domain           = leave_domain_rt,
1392         .pre_schedule           = pre_schedule_rt,
1393         .post_schedule          = post_schedule_rt,
1394         .task_wake_up           = task_wake_up_rt,
1395         .switched_from          = switched_from_rt,
1396 #endif
1397
1398         .set_curr_task          = set_curr_task_rt,
1399         .task_tick              = task_tick_rt,
1400
1401         .prio_changed           = prio_changed_rt,
1402         .switched_to            = switched_to_rt,
1403 };