blob: 10d018212bab8b1ad2f53e1ed388a4bbd56d4656 [file] [log] [blame]
Ingo Molnarbb44e5d2007-07-09 18:51:58 +02001/*
2 * Real-Time Scheduling Class (mapped to the SCHED_FIFO and SCHED_RR
3 * policies)
4 */
5
Gregory Haskins398a1532009-01-14 09:10:04 -05006#ifdef CONFIG_RT_GROUP_SCHED
7
Peter Zijlstraa1ba4d82009-04-01 18:40:15 +02008#define rt_entity_is_task(rt_se) (!(rt_se)->my_q)
9
Peter Zijlstra8f488942009-07-24 12:25:30 +020010static inline struct task_struct *rt_task_of(struct sched_rt_entity *rt_se)
11{
12#ifdef CONFIG_SCHED_DEBUG
13 WARN_ON_ONCE(!rt_entity_is_task(rt_se));
14#endif
15 return container_of(rt_se, struct task_struct, rt);
16}
17
Gregory Haskins398a1532009-01-14 09:10:04 -050018static inline struct rq *rq_of_rt_rq(struct rt_rq *rt_rq)
19{
20 return rt_rq->rq;
21}
22
23static inline struct rt_rq *rt_rq_of_se(struct sched_rt_entity *rt_se)
24{
25 return rt_se->rt_rq;
26}
27
28#else /* CONFIG_RT_GROUP_SCHED */
29
Peter Zijlstraa1ba4d82009-04-01 18:40:15 +020030#define rt_entity_is_task(rt_se) (1)
31
Peter Zijlstra8f488942009-07-24 12:25:30 +020032static inline struct task_struct *rt_task_of(struct sched_rt_entity *rt_se)
33{
34 return container_of(rt_se, struct task_struct, rt);
35}
36
Gregory Haskins398a1532009-01-14 09:10:04 -050037static inline struct rq *rq_of_rt_rq(struct rt_rq *rt_rq)
38{
39 return container_of(rt_rq, struct rq, rt);
40}
41
42static inline struct rt_rq *rt_rq_of_se(struct sched_rt_entity *rt_se)
43{
44 struct task_struct *p = rt_task_of(rt_se);
45 struct rq *rq = task_rq(p);
46
47 return &rq->rt;
48}
49
50#endif /* CONFIG_RT_GROUP_SCHED */
51
Steven Rostedt4fd29172008-01-25 21:08:06 +010052#ifdef CONFIG_SMP
Ingo Molnar84de4272008-01-25 21:08:15 +010053
Gregory Haskins637f5082008-01-25 21:08:18 +010054static inline int rt_overloaded(struct rq *rq)
Steven Rostedt4fd29172008-01-25 21:08:06 +010055{
Gregory Haskins637f5082008-01-25 21:08:18 +010056 return atomic_read(&rq->rd->rto_count);
Steven Rostedt4fd29172008-01-25 21:08:06 +010057}
Ingo Molnar84de4272008-01-25 21:08:15 +010058
Steven Rostedt4fd29172008-01-25 21:08:06 +010059static inline void rt_set_overload(struct rq *rq)
60{
Gregory Haskins1f11eb6a2008-06-04 15:04:05 -040061 if (!rq->online)
62 return;
63
Rusty Russellc6c49272008-11-25 02:35:05 +103064 cpumask_set_cpu(rq->cpu, rq->rd->rto_mask);
Steven Rostedt4fd29172008-01-25 21:08:06 +010065 /*
66 * Make sure the mask is visible before we set
67 * the overload count. That is checked to determine
68 * if we should look at the mask. It would be a shame
69 * if we looked at the mask, but the mask was not
70 * updated yet.
71 */
72 wmb();
Gregory Haskins637f5082008-01-25 21:08:18 +010073 atomic_inc(&rq->rd->rto_count);
Steven Rostedt4fd29172008-01-25 21:08:06 +010074}
Ingo Molnar84de4272008-01-25 21:08:15 +010075
Steven Rostedt4fd29172008-01-25 21:08:06 +010076static inline void rt_clear_overload(struct rq *rq)
77{
Gregory Haskins1f11eb6a2008-06-04 15:04:05 -040078 if (!rq->online)
79 return;
80
Steven Rostedt4fd29172008-01-25 21:08:06 +010081 /* the order here really doesn't matter */
Gregory Haskins637f5082008-01-25 21:08:18 +010082 atomic_dec(&rq->rd->rto_count);
Rusty Russellc6c49272008-11-25 02:35:05 +103083 cpumask_clear_cpu(rq->cpu, rq->rd->rto_mask);
Steven Rostedt4fd29172008-01-25 21:08:06 +010084}
Gregory Haskins73fe6aa2008-01-25 21:08:07 +010085
Gregory Haskins398a1532009-01-14 09:10:04 -050086static void update_rt_migration(struct rt_rq *rt_rq)
Gregory Haskins73fe6aa2008-01-25 21:08:07 +010087{
Peter Zijlstraa1ba4d82009-04-01 18:40:15 +020088 if (rt_rq->rt_nr_migratory && rt_rq->rt_nr_total > 1) {
Gregory Haskins398a1532009-01-14 09:10:04 -050089 if (!rt_rq->overloaded) {
90 rt_set_overload(rq_of_rt_rq(rt_rq));
91 rt_rq->overloaded = 1;
Gregory Haskinscdc8eb92008-01-25 21:08:23 +010092 }
Gregory Haskins398a1532009-01-14 09:10:04 -050093 } else if (rt_rq->overloaded) {
94 rt_clear_overload(rq_of_rt_rq(rt_rq));
95 rt_rq->overloaded = 0;
Gregory Haskins637f5082008-01-25 21:08:18 +010096 }
Gregory Haskins73fe6aa2008-01-25 21:08:07 +010097}
Steven Rostedt4fd29172008-01-25 21:08:06 +010098
Gregory Haskins398a1532009-01-14 09:10:04 -050099static void inc_rt_migration(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
Peter Zijlstrafa85ae22008-01-25 21:08:29 +0100100{
Peter Zijlstraa1ba4d82009-04-01 18:40:15 +0200101 if (!rt_entity_is_task(rt_se))
102 return;
103
104 rt_rq = &rq_of_rt_rq(rt_rq)->rt;
105
106 rt_rq->rt_nr_total++;
Gregory Haskins398a1532009-01-14 09:10:04 -0500107 if (rt_se->nr_cpus_allowed > 1)
108 rt_rq->rt_nr_migratory++;
109
110 update_rt_migration(rt_rq);
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100111}
112
Gregory Haskins398a1532009-01-14 09:10:04 -0500113static void dec_rt_migration(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
114{
Peter Zijlstraa1ba4d82009-04-01 18:40:15 +0200115 if (!rt_entity_is_task(rt_se))
116 return;
117
118 rt_rq = &rq_of_rt_rq(rt_rq)->rt;
119
120 rt_rq->rt_nr_total--;
Gregory Haskins398a1532009-01-14 09:10:04 -0500121 if (rt_se->nr_cpus_allowed > 1)
122 rt_rq->rt_nr_migratory--;
123
124 update_rt_migration(rt_rq);
125}
126
Gregory Haskins917b6272008-12-29 09:39:53 -0500127static void enqueue_pushable_task(struct rq *rq, struct task_struct *p)
128{
129 plist_del(&p->pushable_tasks, &rq->rt.pushable_tasks);
130 plist_node_init(&p->pushable_tasks, p->prio);
131 plist_add(&p->pushable_tasks, &rq->rt.pushable_tasks);
132}
133
134static void dequeue_pushable_task(struct rq *rq, struct task_struct *p)
135{
136 plist_del(&p->pushable_tasks, &rq->rt.pushable_tasks);
137}
138
Ingo Molnarbcf08df2008-04-19 12:11:10 +0200139static inline int has_pushable_tasks(struct rq *rq)
140{
141 return !plist_head_empty(&rq->rt.pushable_tasks);
142}
143
Gregory Haskins917b6272008-12-29 09:39:53 -0500144#else
145
Peter Zijlstraceacc2c2009-01-16 14:46:40 +0100146static inline void enqueue_pushable_task(struct rq *rq, struct task_struct *p)
147{
148}
149
150static inline void dequeue_pushable_task(struct rq *rq, struct task_struct *p)
151{
152}
153
Gregory Haskinsb07430a2009-01-14 08:55:39 -0500154static inline
Peter Zijlstraceacc2c2009-01-16 14:46:40 +0100155void inc_rt_migration(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
156{
157}
158
Gregory Haskinsb07430a2009-01-14 08:55:39 -0500159static inline
Peter Zijlstraceacc2c2009-01-16 14:46:40 +0100160void dec_rt_migration(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
161{
162}
Gregory Haskins917b6272008-12-29 09:39:53 -0500163
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200164#endif /* CONFIG_SMP */
165
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100166static inline int on_rt_rq(struct sched_rt_entity *rt_se)
167{
168 return !list_empty(&rt_se->run_list);
169}
170
Peter Zijlstra052f1dc2008-02-13 15:45:40 +0100171#ifdef CONFIG_RT_GROUP_SCHED
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100172
Peter Zijlstra9f0c1e52008-02-13 15:45:39 +0100173static inline u64 sched_rt_runtime(struct rt_rq *rt_rq)
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100174{
175 if (!rt_rq->tg)
Peter Zijlstra9f0c1e52008-02-13 15:45:39 +0100176 return RUNTIME_INF;
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100177
Peter Zijlstraac086bc2008-04-19 19:44:58 +0200178 return rt_rq->rt_runtime;
179}
180
181static inline u64 sched_rt_period(struct rt_rq *rt_rq)
182{
183 return ktime_to_ns(rt_rq->tg->rt_bandwidth.rt_period);
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100184}
185
Cheng Xuec514c42011-05-14 14:20:02 +0800186typedef struct task_group *rt_rq_iter_t;
187
188#define for_each_rt_rq(rt_rq, iter, rq) \
189 for (iter = list_entry_rcu(task_groups.next, typeof(*iter), list); \
190 (&iter->list != &task_groups) && \
191 (rt_rq = iter->rt_rq[cpu_of(rq)]); \
192 iter = list_entry_rcu(iter->list.next, typeof(*iter), list))
193
Peter Zijlstra3d4b47b2010-11-15 15:47:01 -0800194static inline void list_add_leaf_rt_rq(struct rt_rq *rt_rq)
195{
196 list_add_rcu(&rt_rq->leaf_rt_rq_list,
197 &rq_of_rt_rq(rt_rq)->leaf_rt_rq_list);
198}
199
200static inline void list_del_leaf_rt_rq(struct rt_rq *rt_rq)
201{
202 list_del_rcu(&rt_rq->leaf_rt_rq_list);
203}
204
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100205#define for_each_leaf_rt_rq(rt_rq, rq) \
Bharata B Rao80f40ee2008-12-15 11:56:48 +0530206 list_for_each_entry_rcu(rt_rq, &rq->leaf_rt_rq_list, leaf_rt_rq_list)
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100207
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100208#define for_each_sched_rt_entity(rt_se) \
209 for (; rt_se; rt_se = rt_se->parent)
210
211static inline struct rt_rq *group_rt_rq(struct sched_rt_entity *rt_se)
212{
213 return rt_se->my_q;
214}
215
Thomas Gleixner37dad3f2010-01-20 20:59:01 +0000216static void enqueue_rt_entity(struct sched_rt_entity *rt_se, bool head);
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100217static void dequeue_rt_entity(struct sched_rt_entity *rt_se);
218
Peter Zijlstra9f0c1e52008-02-13 15:45:39 +0100219static void sched_rt_rq_enqueue(struct rt_rq *rt_rq)
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100220{
Dario Faggiolif6121f42008-10-03 17:40:46 +0200221 struct task_struct *curr = rq_of_rt_rq(rt_rq)->curr;
Yong Zhang74b7eb52010-01-29 14:57:52 +0800222 struct sched_rt_entity *rt_se;
223
Balbir Singh0c3b9162011-03-03 17:04:35 +0530224 int cpu = cpu_of(rq_of_rt_rq(rt_rq));
225
226 rt_se = rt_rq->tg->rt_se[cpu];
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100227
Dario Faggiolif6121f42008-10-03 17:40:46 +0200228 if (rt_rq->rt_nr_running) {
229 if (rt_se && !on_rt_rq(rt_se))
Thomas Gleixner37dad3f2010-01-20 20:59:01 +0000230 enqueue_rt_entity(rt_se, false);
Gregory Haskinse864c492008-12-29 09:39:49 -0500231 if (rt_rq->highest_prio.curr < curr->prio)
Peter Zijlstra10203872008-01-25 21:08:32 +0100232 resched_task(curr);
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100233 }
234}
235
Peter Zijlstra9f0c1e52008-02-13 15:45:39 +0100236static void sched_rt_rq_dequeue(struct rt_rq *rt_rq)
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100237{
Yong Zhang74b7eb52010-01-29 14:57:52 +0800238 struct sched_rt_entity *rt_se;
Balbir Singh0c3b9162011-03-03 17:04:35 +0530239 int cpu = cpu_of(rq_of_rt_rq(rt_rq));
Yong Zhang74b7eb52010-01-29 14:57:52 +0800240
Balbir Singh0c3b9162011-03-03 17:04:35 +0530241 rt_se = rt_rq->tg->rt_se[cpu];
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100242
243 if (rt_se && on_rt_rq(rt_se))
244 dequeue_rt_entity(rt_se);
245}
246
Peter Zijlstra23b0fdf2008-02-13 15:45:39 +0100247static inline int rt_rq_throttled(struct rt_rq *rt_rq)
248{
249 return rt_rq->rt_throttled && !rt_rq->rt_nr_boosted;
250}
251
252static int rt_se_boosted(struct sched_rt_entity *rt_se)
253{
254 struct rt_rq *rt_rq = group_rt_rq(rt_se);
255 struct task_struct *p;
256
257 if (rt_rq)
258 return !!rt_rq->rt_nr_boosted;
259
260 p = rt_task_of(rt_se);
261 return p->prio != p->normal_prio;
262}
263
Peter Zijlstrad0b27fa2008-04-19 19:44:57 +0200264#ifdef CONFIG_SMP
Rusty Russellc6c49272008-11-25 02:35:05 +1030265static inline const struct cpumask *sched_rt_period_mask(void)
Peter Zijlstrad0b27fa2008-04-19 19:44:57 +0200266{
267 return cpu_rq(smp_processor_id())->rd->span;
268}
269#else
Rusty Russellc6c49272008-11-25 02:35:05 +1030270static inline const struct cpumask *sched_rt_period_mask(void)
Peter Zijlstrad0b27fa2008-04-19 19:44:57 +0200271{
Rusty Russellc6c49272008-11-25 02:35:05 +1030272 return cpu_online_mask;
Peter Zijlstrad0b27fa2008-04-19 19:44:57 +0200273}
274#endif
275
276static inline
277struct rt_rq *sched_rt_period_rt_rq(struct rt_bandwidth *rt_b, int cpu)
278{
279 return container_of(rt_b, struct task_group, rt_bandwidth)->rt_rq[cpu];
280}
281
Peter Zijlstraac086bc2008-04-19 19:44:58 +0200282static inline struct rt_bandwidth *sched_rt_bandwidth(struct rt_rq *rt_rq)
283{
284 return &rt_rq->tg->rt_bandwidth;
285}
286
Dhaval Giani55e12e52008-06-24 23:39:43 +0530287#else /* !CONFIG_RT_GROUP_SCHED */
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100288
Peter Zijlstra9f0c1e52008-02-13 15:45:39 +0100289static inline u64 sched_rt_runtime(struct rt_rq *rt_rq)
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100290{
Peter Zijlstraac086bc2008-04-19 19:44:58 +0200291 return rt_rq->rt_runtime;
292}
293
294static inline u64 sched_rt_period(struct rt_rq *rt_rq)
295{
296 return ktime_to_ns(def_rt_bandwidth.rt_period);
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100297}
298
Cheng Xuec514c42011-05-14 14:20:02 +0800299typedef struct rt_rq *rt_rq_iter_t;
300
301#define for_each_rt_rq(rt_rq, iter, rq) \
302 for ((void) iter, rt_rq = &rq->rt; rt_rq; rt_rq = NULL)
303
Peter Zijlstra3d4b47b2010-11-15 15:47:01 -0800304static inline void list_add_leaf_rt_rq(struct rt_rq *rt_rq)
305{
306}
307
308static inline void list_del_leaf_rt_rq(struct rt_rq *rt_rq)
309{
310}
311
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100312#define for_each_leaf_rt_rq(rt_rq, rq) \
313 for (rt_rq = &rq->rt; rt_rq; rt_rq = NULL)
314
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100315#define for_each_sched_rt_entity(rt_se) \
316 for (; rt_se; rt_se = NULL)
317
318static inline struct rt_rq *group_rt_rq(struct sched_rt_entity *rt_se)
319{
320 return NULL;
321}
322
Peter Zijlstra9f0c1e52008-02-13 15:45:39 +0100323static inline void sched_rt_rq_enqueue(struct rt_rq *rt_rq)
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100324{
John Blackwoodf3ade832008-08-26 15:09:43 -0400325 if (rt_rq->rt_nr_running)
326 resched_task(rq_of_rt_rq(rt_rq)->curr);
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100327}
328
Peter Zijlstra9f0c1e52008-02-13 15:45:39 +0100329static inline void sched_rt_rq_dequeue(struct rt_rq *rt_rq)
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100330{
331}
332
Peter Zijlstra23b0fdf2008-02-13 15:45:39 +0100333static inline int rt_rq_throttled(struct rt_rq *rt_rq)
334{
335 return rt_rq->rt_throttled;
336}
Peter Zijlstrad0b27fa2008-04-19 19:44:57 +0200337
Rusty Russellc6c49272008-11-25 02:35:05 +1030338static inline const struct cpumask *sched_rt_period_mask(void)
Peter Zijlstrad0b27fa2008-04-19 19:44:57 +0200339{
Rusty Russellc6c49272008-11-25 02:35:05 +1030340 return cpu_online_mask;
Peter Zijlstrad0b27fa2008-04-19 19:44:57 +0200341}
342
343static inline
344struct rt_rq *sched_rt_period_rt_rq(struct rt_bandwidth *rt_b, int cpu)
345{
346 return &cpu_rq(cpu)->rt;
347}
348
Peter Zijlstraac086bc2008-04-19 19:44:58 +0200349static inline struct rt_bandwidth *sched_rt_bandwidth(struct rt_rq *rt_rq)
350{
351 return &def_rt_bandwidth;
352}
353
Dhaval Giani55e12e52008-06-24 23:39:43 +0530354#endif /* CONFIG_RT_GROUP_SCHED */
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100355
Peter Zijlstrab79f3832008-06-19 14:22:25 +0200356#ifdef CONFIG_SMP
Peter Zijlstra78333cd2008-09-23 15:33:43 +0200357/*
358 * We ran out of runtime, see if we can borrow some from our neighbours.
359 */
Peter Zijlstrab79f3832008-06-19 14:22:25 +0200360static int do_balance_runtime(struct rt_rq *rt_rq)
Peter Zijlstraac086bc2008-04-19 19:44:58 +0200361{
362 struct rt_bandwidth *rt_b = sched_rt_bandwidth(rt_rq);
363 struct root_domain *rd = cpu_rq(smp_processor_id())->rd;
364 int i, weight, more = 0;
365 u64 rt_period;
366
Rusty Russellc6c49272008-11-25 02:35:05 +1030367 weight = cpumask_weight(rd->span);
Peter Zijlstraac086bc2008-04-19 19:44:58 +0200368
Thomas Gleixner0986b112009-11-17 15:32:06 +0100369 raw_spin_lock(&rt_b->rt_runtime_lock);
Peter Zijlstraac086bc2008-04-19 19:44:58 +0200370 rt_period = ktime_to_ns(rt_b->rt_period);
Rusty Russellc6c49272008-11-25 02:35:05 +1030371 for_each_cpu(i, rd->span) {
Peter Zijlstraac086bc2008-04-19 19:44:58 +0200372 struct rt_rq *iter = sched_rt_period_rt_rq(rt_b, i);
373 s64 diff;
374
375 if (iter == rt_rq)
376 continue;
377
Thomas Gleixner0986b112009-11-17 15:32:06 +0100378 raw_spin_lock(&iter->rt_runtime_lock);
Peter Zijlstra78333cd2008-09-23 15:33:43 +0200379 /*
380 * Either all rqs have inf runtime and there's nothing to steal
381 * or __disable_runtime() below sets a specific rq to inf to
382 * indicate its been disabled and disalow stealing.
383 */
Peter Zijlstra7def2be2008-06-05 14:49:58 +0200384 if (iter->rt_runtime == RUNTIME_INF)
385 goto next;
386
Peter Zijlstra78333cd2008-09-23 15:33:43 +0200387 /*
388 * From runqueues with spare time, take 1/n part of their
389 * spare time, but no more than our period.
390 */
Peter Zijlstraac086bc2008-04-19 19:44:58 +0200391 diff = iter->rt_runtime - iter->rt_time;
392 if (diff > 0) {
Peter Zijlstra58838cf2008-07-24 12:43:13 +0200393 diff = div_u64((u64)diff, weight);
Peter Zijlstraac086bc2008-04-19 19:44:58 +0200394 if (rt_rq->rt_runtime + diff > rt_period)
395 diff = rt_period - rt_rq->rt_runtime;
396 iter->rt_runtime -= diff;
397 rt_rq->rt_runtime += diff;
398 more = 1;
399 if (rt_rq->rt_runtime == rt_period) {
Thomas Gleixner0986b112009-11-17 15:32:06 +0100400 raw_spin_unlock(&iter->rt_runtime_lock);
Peter Zijlstraac086bc2008-04-19 19:44:58 +0200401 break;
402 }
403 }
Peter Zijlstra7def2be2008-06-05 14:49:58 +0200404next:
Thomas Gleixner0986b112009-11-17 15:32:06 +0100405 raw_spin_unlock(&iter->rt_runtime_lock);
Peter Zijlstraac086bc2008-04-19 19:44:58 +0200406 }
Thomas Gleixner0986b112009-11-17 15:32:06 +0100407 raw_spin_unlock(&rt_b->rt_runtime_lock);
Peter Zijlstraac086bc2008-04-19 19:44:58 +0200408
409 return more;
410}
Peter Zijlstra7def2be2008-06-05 14:49:58 +0200411
Peter Zijlstra78333cd2008-09-23 15:33:43 +0200412/*
413 * Ensure this RQ takes back all the runtime it lend to its neighbours.
414 */
Peter Zijlstra7def2be2008-06-05 14:49:58 +0200415static void __disable_runtime(struct rq *rq)
416{
417 struct root_domain *rd = rq->rd;
Cheng Xuec514c42011-05-14 14:20:02 +0800418 rt_rq_iter_t iter;
Peter Zijlstra7def2be2008-06-05 14:49:58 +0200419 struct rt_rq *rt_rq;
420
421 if (unlikely(!scheduler_running))
422 return;
423
Cheng Xuec514c42011-05-14 14:20:02 +0800424 for_each_rt_rq(rt_rq, iter, rq) {
Peter Zijlstra7def2be2008-06-05 14:49:58 +0200425 struct rt_bandwidth *rt_b = sched_rt_bandwidth(rt_rq);
426 s64 want;
427 int i;
428
Thomas Gleixner0986b112009-11-17 15:32:06 +0100429 raw_spin_lock(&rt_b->rt_runtime_lock);
430 raw_spin_lock(&rt_rq->rt_runtime_lock);
Peter Zijlstra78333cd2008-09-23 15:33:43 +0200431 /*
432 * Either we're all inf and nobody needs to borrow, or we're
433 * already disabled and thus have nothing to do, or we have
434 * exactly the right amount of runtime to take out.
435 */
Peter Zijlstra7def2be2008-06-05 14:49:58 +0200436 if (rt_rq->rt_runtime == RUNTIME_INF ||
437 rt_rq->rt_runtime == rt_b->rt_runtime)
438 goto balanced;
Thomas Gleixner0986b112009-11-17 15:32:06 +0100439 raw_spin_unlock(&rt_rq->rt_runtime_lock);
Peter Zijlstra7def2be2008-06-05 14:49:58 +0200440
Peter Zijlstra78333cd2008-09-23 15:33:43 +0200441 /*
442 * Calculate the difference between what we started out with
443 * and what we current have, that's the amount of runtime
444 * we lend and now have to reclaim.
445 */
Peter Zijlstra7def2be2008-06-05 14:49:58 +0200446 want = rt_b->rt_runtime - rt_rq->rt_runtime;
447
Peter Zijlstra78333cd2008-09-23 15:33:43 +0200448 /*
449 * Greedy reclaim, take back as much as we can.
450 */
Rusty Russellc6c49272008-11-25 02:35:05 +1030451 for_each_cpu(i, rd->span) {
Peter Zijlstra7def2be2008-06-05 14:49:58 +0200452 struct rt_rq *iter = sched_rt_period_rt_rq(rt_b, i);
453 s64 diff;
454
Peter Zijlstra78333cd2008-09-23 15:33:43 +0200455 /*
456 * Can't reclaim from ourselves or disabled runqueues.
457 */
Peter Zijlstraf1679d02008-08-14 15:49:00 +0200458 if (iter == rt_rq || iter->rt_runtime == RUNTIME_INF)
Peter Zijlstra7def2be2008-06-05 14:49:58 +0200459 continue;
460
Thomas Gleixner0986b112009-11-17 15:32:06 +0100461 raw_spin_lock(&iter->rt_runtime_lock);
Peter Zijlstra7def2be2008-06-05 14:49:58 +0200462 if (want > 0) {
463 diff = min_t(s64, iter->rt_runtime, want);
464 iter->rt_runtime -= diff;
465 want -= diff;
466 } else {
467 iter->rt_runtime -= want;
468 want -= want;
469 }
Thomas Gleixner0986b112009-11-17 15:32:06 +0100470 raw_spin_unlock(&iter->rt_runtime_lock);
Peter Zijlstra7def2be2008-06-05 14:49:58 +0200471
472 if (!want)
473 break;
474 }
475
Thomas Gleixner0986b112009-11-17 15:32:06 +0100476 raw_spin_lock(&rt_rq->rt_runtime_lock);
Peter Zijlstra78333cd2008-09-23 15:33:43 +0200477 /*
478 * We cannot be left wanting - that would mean some runtime
479 * leaked out of the system.
480 */
Peter Zijlstra7def2be2008-06-05 14:49:58 +0200481 BUG_ON(want);
482balanced:
Peter Zijlstra78333cd2008-09-23 15:33:43 +0200483 /*
484 * Disable all the borrow logic by pretending we have inf
485 * runtime - in which case borrowing doesn't make sense.
486 */
Peter Zijlstra7def2be2008-06-05 14:49:58 +0200487 rt_rq->rt_runtime = RUNTIME_INF;
Thomas Gleixner0986b112009-11-17 15:32:06 +0100488 raw_spin_unlock(&rt_rq->rt_runtime_lock);
489 raw_spin_unlock(&rt_b->rt_runtime_lock);
Peter Zijlstra7def2be2008-06-05 14:49:58 +0200490 }
491}
492
493static void disable_runtime(struct rq *rq)
494{
495 unsigned long flags;
496
Thomas Gleixner05fa7852009-11-17 14:28:38 +0100497 raw_spin_lock_irqsave(&rq->lock, flags);
Peter Zijlstra7def2be2008-06-05 14:49:58 +0200498 __disable_runtime(rq);
Thomas Gleixner05fa7852009-11-17 14:28:38 +0100499 raw_spin_unlock_irqrestore(&rq->lock, flags);
Peter Zijlstra7def2be2008-06-05 14:49:58 +0200500}
501
502static void __enable_runtime(struct rq *rq)
503{
Cheng Xuec514c42011-05-14 14:20:02 +0800504 rt_rq_iter_t iter;
Peter Zijlstra7def2be2008-06-05 14:49:58 +0200505 struct rt_rq *rt_rq;
506
507 if (unlikely(!scheduler_running))
508 return;
509
Peter Zijlstra78333cd2008-09-23 15:33:43 +0200510 /*
511 * Reset each runqueue's bandwidth settings
512 */
Cheng Xuec514c42011-05-14 14:20:02 +0800513 for_each_rt_rq(rt_rq, iter, rq) {
Peter Zijlstra7def2be2008-06-05 14:49:58 +0200514 struct rt_bandwidth *rt_b = sched_rt_bandwidth(rt_rq);
515
Thomas Gleixner0986b112009-11-17 15:32:06 +0100516 raw_spin_lock(&rt_b->rt_runtime_lock);
517 raw_spin_lock(&rt_rq->rt_runtime_lock);
Peter Zijlstra7def2be2008-06-05 14:49:58 +0200518 rt_rq->rt_runtime = rt_b->rt_runtime;
519 rt_rq->rt_time = 0;
Zhang, Yanminbaf25732008-09-09 11:26:33 +0800520 rt_rq->rt_throttled = 0;
Thomas Gleixner0986b112009-11-17 15:32:06 +0100521 raw_spin_unlock(&rt_rq->rt_runtime_lock);
522 raw_spin_unlock(&rt_b->rt_runtime_lock);
Peter Zijlstra7def2be2008-06-05 14:49:58 +0200523 }
524}
525
526static void enable_runtime(struct rq *rq)
527{
528 unsigned long flags;
529
Thomas Gleixner05fa7852009-11-17 14:28:38 +0100530 raw_spin_lock_irqsave(&rq->lock, flags);
Peter Zijlstra7def2be2008-06-05 14:49:58 +0200531 __enable_runtime(rq);
Thomas Gleixner05fa7852009-11-17 14:28:38 +0100532 raw_spin_unlock_irqrestore(&rq->lock, flags);
Peter Zijlstra7def2be2008-06-05 14:49:58 +0200533}
534
Peter Zijlstraeff65492008-06-19 14:22:26 +0200535static int balance_runtime(struct rt_rq *rt_rq)
536{
537 int more = 0;
538
539 if (rt_rq->rt_time > rt_rq->rt_runtime) {
Thomas Gleixner0986b112009-11-17 15:32:06 +0100540 raw_spin_unlock(&rt_rq->rt_runtime_lock);
Peter Zijlstraeff65492008-06-19 14:22:26 +0200541 more = do_balance_runtime(rt_rq);
Thomas Gleixner0986b112009-11-17 15:32:06 +0100542 raw_spin_lock(&rt_rq->rt_runtime_lock);
Peter Zijlstraeff65492008-06-19 14:22:26 +0200543 }
544
545 return more;
546}
Dhaval Giani55e12e52008-06-24 23:39:43 +0530547#else /* !CONFIG_SMP */
Peter Zijlstraeff65492008-06-19 14:22:26 +0200548static inline int balance_runtime(struct rt_rq *rt_rq)
549{
550 return 0;
551}
Dhaval Giani55e12e52008-06-24 23:39:43 +0530552#endif /* CONFIG_SMP */
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100553
554static int do_sched_rt_period_timer(struct rt_bandwidth *rt_b, int overrun)
555{
556 int i, idle = 1;
Rusty Russellc6c49272008-11-25 02:35:05 +1030557 const struct cpumask *span;
Peter Zijlstrad0b27fa2008-04-19 19:44:57 +0200558
Peter Zijlstra0b148fa2008-08-19 12:33:04 +0200559 if (!rt_bandwidth_enabled() || rt_b->rt_runtime == RUNTIME_INF)
Peter Zijlstrad0b27fa2008-04-19 19:44:57 +0200560 return 1;
561
562 span = sched_rt_period_mask();
Rusty Russellc6c49272008-11-25 02:35:05 +1030563 for_each_cpu(i, span) {
Peter Zijlstrad0b27fa2008-04-19 19:44:57 +0200564 int enqueue = 0;
565 struct rt_rq *rt_rq = sched_rt_period_rt_rq(rt_b, i);
566 struct rq *rq = rq_of_rt_rq(rt_rq);
567
Thomas Gleixner05fa7852009-11-17 14:28:38 +0100568 raw_spin_lock(&rq->lock);
Peter Zijlstrad0b27fa2008-04-19 19:44:57 +0200569 if (rt_rq->rt_time) {
570 u64 runtime;
571
Thomas Gleixner0986b112009-11-17 15:32:06 +0100572 raw_spin_lock(&rt_rq->rt_runtime_lock);
Peter Zijlstraeff65492008-06-19 14:22:26 +0200573 if (rt_rq->rt_throttled)
574 balance_runtime(rt_rq);
Peter Zijlstrad0b27fa2008-04-19 19:44:57 +0200575 runtime = rt_rq->rt_runtime;
576 rt_rq->rt_time -= min(rt_rq->rt_time, overrun*runtime);
577 if (rt_rq->rt_throttled && rt_rq->rt_time < runtime) {
578 rt_rq->rt_throttled = 0;
579 enqueue = 1;
Mike Galbraith61eadef2011-04-29 08:36:50 +0200580
581 /*
582 * Force a clock update if the CPU was idle,
583 * lest wakeup -> unthrottle time accumulate.
584 */
585 if (rt_rq->rt_nr_running && rq->curr == rq->idle)
586 rq->skip_clock_update = -1;
Peter Zijlstrad0b27fa2008-04-19 19:44:57 +0200587 }
588 if (rt_rq->rt_time || rt_rq->rt_nr_running)
589 idle = 0;
Thomas Gleixner0986b112009-11-17 15:32:06 +0100590 raw_spin_unlock(&rt_rq->rt_runtime_lock);
Balbir Singh0c3b9162011-03-03 17:04:35 +0530591 } else if (rt_rq->rt_nr_running) {
Peter Zijlstra8a8cde12008-06-19 14:22:28 +0200592 idle = 0;
Balbir Singh0c3b9162011-03-03 17:04:35 +0530593 if (!rt_rq_throttled(rt_rq))
594 enqueue = 1;
595 }
Peter Zijlstrad0b27fa2008-04-19 19:44:57 +0200596
597 if (enqueue)
598 sched_rt_rq_enqueue(rt_rq);
Thomas Gleixner05fa7852009-11-17 14:28:38 +0100599 raw_spin_unlock(&rq->lock);
Peter Zijlstrad0b27fa2008-04-19 19:44:57 +0200600 }
601
602 return idle;
603}
604
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100605static inline int rt_se_prio(struct sched_rt_entity *rt_se)
606{
Peter Zijlstra052f1dc2008-02-13 15:45:40 +0100607#ifdef CONFIG_RT_GROUP_SCHED
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100608 struct rt_rq *rt_rq = group_rt_rq(rt_se);
609
610 if (rt_rq)
Gregory Haskinse864c492008-12-29 09:39:49 -0500611 return rt_rq->highest_prio.curr;
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100612#endif
613
614 return rt_task_of(rt_se)->prio;
615}
616
Peter Zijlstra9f0c1e52008-02-13 15:45:39 +0100617static int sched_rt_runtime_exceeded(struct rt_rq *rt_rq)
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100618{
Peter Zijlstra9f0c1e52008-02-13 15:45:39 +0100619 u64 runtime = sched_rt_runtime(rt_rq);
Peter Zijlstrafa85ae22008-01-25 21:08:29 +0100620
Peter Zijlstrafa85ae22008-01-25 21:08:29 +0100621 if (rt_rq->rt_throttled)
Peter Zijlstra23b0fdf2008-02-13 15:45:39 +0100622 return rt_rq_throttled(rt_rq);
Peter Zijlstrafa85ae22008-01-25 21:08:29 +0100623
Peter Zijlstraac086bc2008-04-19 19:44:58 +0200624 if (sched_rt_runtime(rt_rq) >= sched_rt_period(rt_rq))
625 return 0;
626
Peter Zijlstrab79f3832008-06-19 14:22:25 +0200627 balance_runtime(rt_rq);
628 runtime = sched_rt_runtime(rt_rq);
629 if (runtime == RUNTIME_INF)
630 return 0;
Peter Zijlstraac086bc2008-04-19 19:44:58 +0200631
Peter Zijlstra9f0c1e52008-02-13 15:45:39 +0100632 if (rt_rq->rt_time > runtime) {
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100633 rt_rq->rt_throttled = 1;
Peter Zijlstra23b0fdf2008-02-13 15:45:39 +0100634 if (rt_rq_throttled(rt_rq)) {
Peter Zijlstra9f0c1e52008-02-13 15:45:39 +0100635 sched_rt_rq_dequeue(rt_rq);
Peter Zijlstra23b0fdf2008-02-13 15:45:39 +0100636 return 1;
637 }
Peter Zijlstrafa85ae22008-01-25 21:08:29 +0100638 }
639
640 return 0;
641}
642
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200643/*
644 * Update the current task's runtime statistics. Skip current tasks that
645 * are not in our scheduling class.
646 */
Alexey Dobriyana9957442007-10-15 17:00:13 +0200647static void update_curr_rt(struct rq *rq)
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200648{
649 struct task_struct *curr = rq->curr;
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100650 struct sched_rt_entity *rt_se = &curr->rt;
651 struct rt_rq *rt_rq = rt_rq_of_se(rt_se);
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200652 u64 delta_exec;
653
Peter Zijlstra06c3bc62011-02-02 13:19:48 +0100654 if (curr->sched_class != &rt_sched_class)
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200655 return;
656
Venkatesh Pallipadi305e6832010-10-04 17:03:21 -0700657 delta_exec = rq->clock_task - curr->se.exec_start;
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200658 if (unlikely((s64)delta_exec < 0))
659 delta_exec = 0;
Ingo Molnar6cfb0d52007-08-02 17:41:40 +0200660
Lucas De Marchi41acab82010-03-10 23:37:45 -0300661 schedstat_set(curr->se.statistics.exec_max, max(curr->se.statistics.exec_max, delta_exec));
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200662
663 curr->se.sum_exec_runtime += delta_exec;
Frank Mayharf06febc2008-09-12 09:54:39 -0700664 account_group_exec_runtime(curr, delta_exec);
665
Venkatesh Pallipadi305e6832010-10-04 17:03:21 -0700666 curr->se.exec_start = rq->clock_task;
Srivatsa Vaddagirid842de82007-12-02 20:04:49 +0100667 cpuacct_charge(curr, delta_exec);
Peter Zijlstrafa85ae22008-01-25 21:08:29 +0100668
Peter Zijlstrae9e92502009-09-01 10:34:37 +0200669 sched_rt_avg_update(rq, delta_exec);
670
Peter Zijlstra0b148fa2008-08-19 12:33:04 +0200671 if (!rt_bandwidth_enabled())
672 return;
673
Dhaval Giani354d60c2008-04-19 19:44:59 +0200674 for_each_sched_rt_entity(rt_se) {
675 rt_rq = rt_rq_of_se(rt_se);
676
Peter Zijlstracc2991c2008-08-19 12:33:03 +0200677 if (sched_rt_runtime(rt_rq) != RUNTIME_INF) {
Thomas Gleixner0986b112009-11-17 15:32:06 +0100678 raw_spin_lock(&rt_rq->rt_runtime_lock);
Peter Zijlstracc2991c2008-08-19 12:33:03 +0200679 rt_rq->rt_time += delta_exec;
680 if (sched_rt_runtime_exceeded(rt_rq))
681 resched_task(curr);
Thomas Gleixner0986b112009-11-17 15:32:06 +0100682 raw_spin_unlock(&rt_rq->rt_runtime_lock);
Peter Zijlstracc2991c2008-08-19 12:33:03 +0200683 }
Dhaval Giani354d60c2008-04-19 19:44:59 +0200684 }
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200685}
686
Gregory Haskins398a1532009-01-14 09:10:04 -0500687#if defined CONFIG_SMP
Gregory Haskinse864c492008-12-29 09:39:49 -0500688
689static struct task_struct *pick_next_highest_task_rt(struct rq *rq, int cpu);
690
691static inline int next_prio(struct rq *rq)
Steven Rostedt63489e42008-01-25 21:08:03 +0100692{
Gregory Haskinse864c492008-12-29 09:39:49 -0500693 struct task_struct *next = pick_next_highest_task_rt(rq, rq->cpu);
Gregory Haskins1f11eb6a2008-06-04 15:04:05 -0400694
Gregory Haskinse864c492008-12-29 09:39:49 -0500695 if (next && rt_prio(next->prio))
696 return next->prio;
697 else
698 return MAX_RT_PRIO;
699}
Gregory Haskinse864c492008-12-29 09:39:49 -0500700
Gregory Haskins398a1532009-01-14 09:10:04 -0500701static void
702inc_rt_prio_smp(struct rt_rq *rt_rq, int prio, int prev_prio)
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200703{
Gregory Haskins4d984272008-12-29 09:39:49 -0500704 struct rq *rq = rq_of_rt_rq(rt_rq);
Gregory Haskins4d984272008-12-29 09:39:49 -0500705
Gregory Haskins398a1532009-01-14 09:10:04 -0500706 if (prio < prev_prio) {
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100707
Gregory Haskinse864c492008-12-29 09:39:49 -0500708 /*
709 * If the new task is higher in priority than anything on the
Gregory Haskins398a1532009-01-14 09:10:04 -0500710 * run-queue, we know that the previous high becomes our
711 * next-highest.
Gregory Haskinse864c492008-12-29 09:39:49 -0500712 */
Gregory Haskins398a1532009-01-14 09:10:04 -0500713 rt_rq->highest_prio.next = prev_prio;
714
Gregory Haskins1f11eb6a2008-06-04 15:04:05 -0400715 if (rq->online)
Gregory Haskins4d984272008-12-29 09:39:49 -0500716 cpupri_set(&rq->rd->cpupri, rq->cpu, prio);
Ingo Molnar1100ac92008-06-05 12:25:37 +0200717
Gregory Haskinse864c492008-12-29 09:39:49 -0500718 } else if (prio == rt_rq->highest_prio.curr)
719 /*
720 * If the next task is equal in priority to the highest on
721 * the run-queue, then we implicitly know that the next highest
722 * task cannot be any lower than current
723 */
724 rt_rq->highest_prio.next = prio;
725 else if (prio < rt_rq->highest_prio.next)
726 /*
727 * Otherwise, we need to recompute next-highest
728 */
729 rt_rq->highest_prio.next = next_prio(rq);
Steven Rostedt63489e42008-01-25 21:08:03 +0100730}
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100731
Gregory Haskins398a1532009-01-14 09:10:04 -0500732static void
733dec_rt_prio_smp(struct rt_rq *rt_rq, int prio, int prev_prio)
Steven Rostedt63489e42008-01-25 21:08:03 +0100734{
Gregory Haskins4d984272008-12-29 09:39:49 -0500735 struct rq *rq = rq_of_rt_rq(rt_rq);
Gregory Haskins6e0534f2008-05-12 21:21:01 +0200736
Gregory Haskins398a1532009-01-14 09:10:04 -0500737 if (rt_rq->rt_nr_running && (prio <= rt_rq->highest_prio.next))
738 rt_rq->highest_prio.next = next_prio(rq);
739
740 if (rq->online && rt_rq->highest_prio.curr != prev_prio)
741 cpupri_set(&rq->rd->cpupri, rq->cpu, rt_rq->highest_prio.curr);
742}
743
744#else /* CONFIG_SMP */
745
746static inline
747void inc_rt_prio_smp(struct rt_rq *rt_rq, int prio, int prev_prio) {}
748static inline
749void dec_rt_prio_smp(struct rt_rq *rt_rq, int prio, int prev_prio) {}
750
751#endif /* CONFIG_SMP */
752
Steven Rostedt63489e42008-01-25 21:08:03 +0100753#if defined CONFIG_SMP || defined CONFIG_RT_GROUP_SCHED
Gregory Haskins398a1532009-01-14 09:10:04 -0500754static void
755inc_rt_prio(struct rt_rq *rt_rq, int prio)
756{
757 int prev_prio = rt_rq->highest_prio.curr;
Steven Rostedt63489e42008-01-25 21:08:03 +0100758
Gregory Haskins398a1532009-01-14 09:10:04 -0500759 if (prio < prev_prio)
760 rt_rq->highest_prio.curr = prio;
761
762 inc_rt_prio_smp(rt_rq, prio, prev_prio);
763}
764
765static void
766dec_rt_prio(struct rt_rq *rt_rq, int prio)
767{
768 int prev_prio = rt_rq->highest_prio.curr;
769
770 if (rt_rq->rt_nr_running) {
771
772 WARN_ON(prio < prev_prio);
Gregory Haskinse864c492008-12-29 09:39:49 -0500773
774 /*
Gregory Haskins398a1532009-01-14 09:10:04 -0500775 * This may have been our highest task, and therefore
776 * we may have some recomputation to do
Gregory Haskinse864c492008-12-29 09:39:49 -0500777 */
Gregory Haskins398a1532009-01-14 09:10:04 -0500778 if (prio == prev_prio) {
Gregory Haskinse864c492008-12-29 09:39:49 -0500779 struct rt_prio_array *array = &rt_rq->active;
780
781 rt_rq->highest_prio.curr =
Steven Rostedt764a9d62008-01-25 21:08:04 +0100782 sched_find_first_bit(array->bitmap);
Gregory Haskinse864c492008-12-29 09:39:49 -0500783 }
784
Steven Rostedt764a9d62008-01-25 21:08:04 +0100785 } else
Gregory Haskinse864c492008-12-29 09:39:49 -0500786 rt_rq->highest_prio.curr = MAX_RT_PRIO;
Gregory Haskins73fe6aa2008-01-25 21:08:07 +0100787
Gregory Haskins398a1532009-01-14 09:10:04 -0500788 dec_rt_prio_smp(rt_rq, prio, prev_prio);
789}
Gregory Haskins1f11eb6a2008-06-04 15:04:05 -0400790
Gregory Haskins398a1532009-01-14 09:10:04 -0500791#else
792
793static inline void inc_rt_prio(struct rt_rq *rt_rq, int prio) {}
794static inline void dec_rt_prio(struct rt_rq *rt_rq, int prio) {}
795
796#endif /* CONFIG_SMP || CONFIG_RT_GROUP_SCHED */
797
Gregory Haskins73fe6aa2008-01-25 21:08:07 +0100798#ifdef CONFIG_RT_GROUP_SCHED
Gregory Haskins398a1532009-01-14 09:10:04 -0500799
800static void
801inc_rt_group(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
802{
Gregory Haskins73fe6aa2008-01-25 21:08:07 +0100803 if (rt_se_boosted(rt_se))
Steven Rostedt764a9d62008-01-25 21:08:04 +0100804 rt_rq->rt_nr_boosted++;
Peter Zijlstra052f1dc2008-02-13 15:45:40 +0100805
Peter Zijlstra23b0fdf2008-02-13 15:45:39 +0100806 if (rt_rq->tg)
807 start_rt_bandwidth(&rt_rq->tg->rt_bandwidth);
Gregory Haskins398a1532009-01-14 09:10:04 -0500808}
809
810static void
811dec_rt_group(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
812{
Peter Zijlstra23b0fdf2008-02-13 15:45:39 +0100813 if (rt_se_boosted(rt_se))
814 rt_rq->rt_nr_boosted--;
815
816 WARN_ON(!rt_rq->rt_nr_running && rt_rq->rt_nr_boosted);
Gregory Haskins398a1532009-01-14 09:10:04 -0500817}
818
819#else /* CONFIG_RT_GROUP_SCHED */
820
821static void
822inc_rt_group(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
823{
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200824 start_rt_bandwidth(&def_rt_bandwidth);
Gregory Haskins398a1532009-01-14 09:10:04 -0500825}
826
827static inline
828void dec_rt_group(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq) {}
829
830#endif /* CONFIG_RT_GROUP_SCHED */
831
832static inline
833void inc_rt_tasks(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
834{
835 int prio = rt_se_prio(rt_se);
836
837 WARN_ON(!rt_prio(prio));
838 rt_rq->rt_nr_running++;
839
840 inc_rt_prio(rt_rq, prio);
841 inc_rt_migration(rt_se, rt_rq);
842 inc_rt_group(rt_se, rt_rq);
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200843}
844
Peter Zijlstra23b0fdf2008-02-13 15:45:39 +0100845static inline
846void dec_rt_tasks(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
847{
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200848 WARN_ON(!rt_prio(rt_se_prio(rt_se)));
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100849 WARN_ON(!rt_rq->rt_nr_running);
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200850 rt_rq->rt_nr_running--;
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200851
Gregory Haskins398a1532009-01-14 09:10:04 -0500852 dec_rt_prio(rt_rq, rt_se_prio(rt_se));
853 dec_rt_migration(rt_se, rt_rq);
854 dec_rt_group(rt_se, rt_rq);
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200855}
856
Thomas Gleixner37dad3f2010-01-20 20:59:01 +0000857static void __enqueue_rt_entity(struct sched_rt_entity *rt_se, bool head)
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200858{
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100859 struct rt_rq *rt_rq = rt_rq_of_se(rt_se);
860 struct rt_prio_array *array = &rt_rq->active;
861 struct rt_rq *group_rq = group_rt_rq(rt_se);
Dmitry Adamushko20b63312008-06-11 00:58:30 +0200862 struct list_head *queue = array->queue + rt_se_prio(rt_se);
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200863
Peter Zijlstraad2a3f12008-06-19 09:06:57 +0200864 /*
865 * Don't enqueue the group if its throttled, or when empty.
866 * The latter is a consequence of the former when a child group
867 * get throttled and the current group doesn't have any other
868 * active members.
869 */
870 if (group_rq && (rt_rq_throttled(group_rq) || !group_rq->rt_nr_running))
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100871 return;
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200872
Peter Zijlstra3d4b47b2010-11-15 15:47:01 -0800873 if (!rt_rq->rt_nr_running)
874 list_add_leaf_rt_rq(rt_rq);
875
Thomas Gleixner37dad3f2010-01-20 20:59:01 +0000876 if (head)
877 list_add(&rt_se->run_list, queue);
878 else
879 list_add_tail(&rt_se->run_list, queue);
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100880 __set_bit(rt_se_prio(rt_se), array->bitmap);
Peter Zijlstra78f2c7d2008-01-25 21:08:27 +0100881
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100882 inc_rt_tasks(rt_se, rt_rq);
883}
884
Peter Zijlstraad2a3f12008-06-19 09:06:57 +0200885static void __dequeue_rt_entity(struct sched_rt_entity *rt_se)
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100886{
887 struct rt_rq *rt_rq = rt_rq_of_se(rt_se);
888 struct rt_prio_array *array = &rt_rq->active;
889
890 list_del_init(&rt_se->run_list);
891 if (list_empty(array->queue + rt_se_prio(rt_se)))
892 __clear_bit(rt_se_prio(rt_se), array->bitmap);
893
894 dec_rt_tasks(rt_se, rt_rq);
Peter Zijlstra3d4b47b2010-11-15 15:47:01 -0800895 if (!rt_rq->rt_nr_running)
896 list_del_leaf_rt_rq(rt_rq);
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100897}
898
899/*
900 * Because the prio of an upper entry depends on the lower
901 * entries, we must remove entries top - down.
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100902 */
Peter Zijlstraad2a3f12008-06-19 09:06:57 +0200903static void dequeue_rt_stack(struct sched_rt_entity *rt_se)
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100904{
Peter Zijlstraad2a3f12008-06-19 09:06:57 +0200905 struct sched_rt_entity *back = NULL;
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100906
Peter Zijlstra58d6c2d2008-04-19 19:45:00 +0200907 for_each_sched_rt_entity(rt_se) {
908 rt_se->back = back;
909 back = rt_se;
910 }
911
912 for (rt_se = back; rt_se; rt_se = rt_se->back) {
913 if (on_rt_rq(rt_se))
Peter Zijlstraad2a3f12008-06-19 09:06:57 +0200914 __dequeue_rt_entity(rt_se);
915 }
916}
917
Thomas Gleixner37dad3f2010-01-20 20:59:01 +0000918static void enqueue_rt_entity(struct sched_rt_entity *rt_se, bool head)
Peter Zijlstraad2a3f12008-06-19 09:06:57 +0200919{
920 dequeue_rt_stack(rt_se);
921 for_each_sched_rt_entity(rt_se)
Thomas Gleixner37dad3f2010-01-20 20:59:01 +0000922 __enqueue_rt_entity(rt_se, head);
Peter Zijlstraad2a3f12008-06-19 09:06:57 +0200923}
924
925static void dequeue_rt_entity(struct sched_rt_entity *rt_se)
926{
927 dequeue_rt_stack(rt_se);
928
929 for_each_sched_rt_entity(rt_se) {
930 struct rt_rq *rt_rq = group_rt_rq(rt_se);
931
932 if (rt_rq && rt_rq->rt_nr_running)
Thomas Gleixner37dad3f2010-01-20 20:59:01 +0000933 __enqueue_rt_entity(rt_se, false);
Peter Zijlstra58d6c2d2008-04-19 19:45:00 +0200934 }
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200935}
936
937/*
938 * Adding/removing a task to/from a priority array:
939 */
Thomas Gleixnerea87bb72010-01-20 20:58:57 +0000940static void
Peter Zijlstra371fd7e2010-03-24 16:38:48 +0100941enqueue_task_rt(struct rq *rq, struct task_struct *p, int flags)
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100942{
943 struct sched_rt_entity *rt_se = &p->rt;
944
Peter Zijlstra371fd7e2010-03-24 16:38:48 +0100945 if (flags & ENQUEUE_WAKEUP)
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100946 rt_se->timeout = 0;
947
Peter Zijlstra371fd7e2010-03-24 16:38:48 +0100948 enqueue_rt_entity(rt_se, flags & ENQUEUE_HEAD);
Peter Zijlstrac09595f2008-06-27 13:41:14 +0200949
Gregory Haskins917b6272008-12-29 09:39:53 -0500950 if (!task_current(rq, p) && p->rt.nr_cpus_allowed > 1)
951 enqueue_pushable_task(rq, p);
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100952}
953
Peter Zijlstra371fd7e2010-03-24 16:38:48 +0100954static void dequeue_task_rt(struct rq *rq, struct task_struct *p, int flags)
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200955{
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100956 struct sched_rt_entity *rt_se = &p->rt;
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200957
958 update_curr_rt(rq);
Peter Zijlstraad2a3f12008-06-19 09:06:57 +0200959 dequeue_rt_entity(rt_se);
Peter Zijlstrac09595f2008-06-27 13:41:14 +0200960
Gregory Haskins917b6272008-12-29 09:39:53 -0500961 dequeue_pushable_task(rq, p);
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200962}
963
964/*
965 * Put task to the end of the run list without the overhead of dequeue
966 * followed by enqueue.
967 */
Dmitry Adamushko7ebefa82008-07-01 23:32:15 +0200968static void
969requeue_rt_entity(struct rt_rq *rt_rq, struct sched_rt_entity *rt_se, int head)
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200970{
Ingo Molnar1cdad712008-06-19 09:09:15 +0200971 if (on_rt_rq(rt_se)) {
Dmitry Adamushko7ebefa82008-07-01 23:32:15 +0200972 struct rt_prio_array *array = &rt_rq->active;
973 struct list_head *queue = array->queue + rt_se_prio(rt_se);
974
975 if (head)
976 list_move(&rt_se->run_list, queue);
977 else
978 list_move_tail(&rt_se->run_list, queue);
Ingo Molnar1cdad712008-06-19 09:09:15 +0200979 }
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200980}
981
Dmitry Adamushko7ebefa82008-07-01 23:32:15 +0200982static void requeue_task_rt(struct rq *rq, struct task_struct *p, int head)
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100983{
984 struct sched_rt_entity *rt_se = &p->rt;
985 struct rt_rq *rt_rq;
986
987 for_each_sched_rt_entity(rt_se) {
988 rt_rq = rt_rq_of_se(rt_se);
Dmitry Adamushko7ebefa82008-07-01 23:32:15 +0200989 requeue_rt_entity(rt_rq, rt_se, head);
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100990 }
991}
992
993static void yield_task_rt(struct rq *rq)
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200994{
Dmitry Adamushko7ebefa82008-07-01 23:32:15 +0200995 requeue_task_rt(rq, rq->curr, 0);
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200996}
997
Gregory Haskinse7693a32008-01-25 21:08:09 +0100998#ifdef CONFIG_SMP
Gregory Haskins318e0892008-01-25 21:08:10 +0100999static int find_lowest_rq(struct task_struct *task);
1000
Peter Zijlstra0017d732010-03-24 18:34:10 +01001001static int
Peter Zijlstra7608dec2011-04-05 17:23:46 +02001002select_task_rq_rt(struct task_struct *p, int sd_flag, int flags)
Gregory Haskinse7693a32008-01-25 21:08:09 +01001003{
Peter Zijlstra7608dec2011-04-05 17:23:46 +02001004 struct task_struct *curr;
1005 struct rq *rq;
1006 int cpu;
1007
Peter Zijlstra0763a662009-09-14 19:37:39 +02001008 if (sd_flag != SD_BALANCE_WAKE)
Peter Zijlstra5f3edc12009-09-10 13:42:00 +02001009 return smp_processor_id();
1010
Peter Zijlstra7608dec2011-04-05 17:23:46 +02001011 cpu = task_cpu(p);
1012 rq = cpu_rq(cpu);
1013
1014 rcu_read_lock();
1015 curr = ACCESS_ONCE(rq->curr); /* unlocked access */
1016
Gregory Haskins318e0892008-01-25 21:08:10 +01001017 /*
Peter Zijlstra7608dec2011-04-05 17:23:46 +02001018 * If the current task on @p's runqueue is an RT task, then
Steven Rostedte1f47d82008-01-25 21:08:12 +01001019 * try to see if we can wake this RT task up on another
1020 * runqueue. Otherwise simply start this RT task
1021 * on its current runqueue.
1022 *
Steven Rostedt43fa5462010-09-20 22:40:03 -04001023 * We want to avoid overloading runqueues. If the woken
1024 * task is a higher priority, then it will stay on this CPU
1025 * and the lower prio task should be moved to another CPU.
1026 * Even though this will probably make the lower prio task
1027 * lose its cache, we do not want to bounce a higher task
1028 * around just because it gave up its CPU, perhaps for a
1029 * lock?
1030 *
1031 * For equal prio tasks, we just let the scheduler sort it out.
Peter Zijlstra7608dec2011-04-05 17:23:46 +02001032 *
Gregory Haskins318e0892008-01-25 21:08:10 +01001033 * Otherwise, just let it ride on the affined RQ and the
1034 * post-schedule router will push the preempted task away
Peter Zijlstra7608dec2011-04-05 17:23:46 +02001035 *
1036 * This test is optimistic, if we get it wrong the load-balancer
1037 * will have to sort it out.
Gregory Haskins318e0892008-01-25 21:08:10 +01001038 */
Peter Zijlstra7608dec2011-04-05 17:23:46 +02001039 if (curr && unlikely(rt_task(curr)) &&
1040 (curr->rt.nr_cpus_allowed < 2 ||
1041 curr->prio < p->prio) &&
1042 (p->rt.nr_cpus_allowed > 1)) {
1043 int target = find_lowest_rq(p);
1044
1045 if (target != -1)
1046 cpu = target;
1047 }
1048 rcu_read_unlock();
1049
1050 return cpu;
Gregory Haskinse7693a32008-01-25 21:08:09 +01001051}
Dmitry Adamushko7ebefa82008-07-01 23:32:15 +02001052
1053static void check_preempt_equal_prio(struct rq *rq, struct task_struct *p)
1054{
Dmitry Adamushko7ebefa82008-07-01 23:32:15 +02001055 if (rq->curr->rt.nr_cpus_allowed == 1)
1056 return;
1057
Rusty Russell13b8bd02009-03-25 15:01:22 +10301058 if (p->rt.nr_cpus_allowed != 1
1059 && cpupri_find(&rq->rd->cpupri, p, NULL))
Dmitry Adamushko7ebefa82008-07-01 23:32:15 +02001060 return;
1061
Rusty Russell13b8bd02009-03-25 15:01:22 +10301062 if (!cpupri_find(&rq->rd->cpupri, rq->curr, NULL))
1063 return;
Dmitry Adamushko7ebefa82008-07-01 23:32:15 +02001064
1065 /*
1066 * There appears to be other cpus that can accept
1067 * current and none to run 'p', so lets reschedule
1068 * to try and push current away:
1069 */
1070 requeue_task_rt(rq, p, 1);
1071 resched_task(rq->curr);
1072}
1073
Gregory Haskinse7693a32008-01-25 21:08:09 +01001074#endif /* CONFIG_SMP */
1075
Ingo Molnarbb44e5d2007-07-09 18:51:58 +02001076/*
1077 * Preempt the current task with a newly woken task if needed:
1078 */
Peter Zijlstra7d478722009-09-14 19:55:44 +02001079static void check_preempt_curr_rt(struct rq *rq, struct task_struct *p, int flags)
Ingo Molnarbb44e5d2007-07-09 18:51:58 +02001080{
Gregory Haskins45c01e82008-05-12 21:20:41 +02001081 if (p->prio < rq->curr->prio) {
Ingo Molnarbb44e5d2007-07-09 18:51:58 +02001082 resched_task(rq->curr);
Gregory Haskins45c01e82008-05-12 21:20:41 +02001083 return;
1084 }
1085
1086#ifdef CONFIG_SMP
1087 /*
1088 * If:
1089 *
1090 * - the newly woken task is of equal priority to the current task
1091 * - the newly woken task is non-migratable while current is migratable
1092 * - current will be preempted on the next reschedule
1093 *
1094 * we should check to see if current can readily move to a different
1095 * cpu. If so, we will reschedule to allow the push logic to try
1096 * to move current somewhere else, making room for our non-migratable
1097 * task.
1098 */
Hillf Danton8dd0de82011-06-14 18:36:24 -04001099 if (p->prio == rq->curr->prio && !test_tsk_need_resched(rq->curr))
Dmitry Adamushko7ebefa82008-07-01 23:32:15 +02001100 check_preempt_equal_prio(rq, p);
Gregory Haskins45c01e82008-05-12 21:20:41 +02001101#endif
Ingo Molnarbb44e5d2007-07-09 18:51:58 +02001102}
1103
Peter Zijlstra6f505b12008-01-25 21:08:30 +01001104static struct sched_rt_entity *pick_next_rt_entity(struct rq *rq,
1105 struct rt_rq *rt_rq)
Ingo Molnarbb44e5d2007-07-09 18:51:58 +02001106{
Peter Zijlstra6f505b12008-01-25 21:08:30 +01001107 struct rt_prio_array *array = &rt_rq->active;
1108 struct sched_rt_entity *next = NULL;
Ingo Molnarbb44e5d2007-07-09 18:51:58 +02001109 struct list_head *queue;
1110 int idx;
1111
1112 idx = sched_find_first_bit(array->bitmap);
Peter Zijlstra6f505b12008-01-25 21:08:30 +01001113 BUG_ON(idx >= MAX_RT_PRIO);
Ingo Molnarbb44e5d2007-07-09 18:51:58 +02001114
1115 queue = array->queue + idx;
Peter Zijlstra6f505b12008-01-25 21:08:30 +01001116 next = list_entry(queue->next, struct sched_rt_entity, run_list);
Dmitry Adamushko326587b2008-01-25 21:08:34 +01001117
Ingo Molnarbb44e5d2007-07-09 18:51:58 +02001118 return next;
1119}
1120
Gregory Haskins917b6272008-12-29 09:39:53 -05001121static struct task_struct *_pick_next_task_rt(struct rq *rq)
Peter Zijlstra6f505b12008-01-25 21:08:30 +01001122{
1123 struct sched_rt_entity *rt_se;
1124 struct task_struct *p;
1125 struct rt_rq *rt_rq;
1126
Peter Zijlstra6f505b12008-01-25 21:08:30 +01001127 rt_rq = &rq->rt;
1128
1129 if (unlikely(!rt_rq->rt_nr_running))
1130 return NULL;
1131
Peter Zijlstra23b0fdf2008-02-13 15:45:39 +01001132 if (rt_rq_throttled(rt_rq))
Peter Zijlstra6f505b12008-01-25 21:08:30 +01001133 return NULL;
1134
1135 do {
1136 rt_se = pick_next_rt_entity(rq, rt_rq);
Dmitry Adamushko326587b2008-01-25 21:08:34 +01001137 BUG_ON(!rt_se);
Peter Zijlstra6f505b12008-01-25 21:08:30 +01001138 rt_rq = group_rt_rq(rt_se);
1139 } while (rt_rq);
1140
1141 p = rt_task_of(rt_se);
Venkatesh Pallipadi305e6832010-10-04 17:03:21 -07001142 p->se.exec_start = rq->clock_task;
Gregory Haskins917b6272008-12-29 09:39:53 -05001143
1144 return p;
1145}
1146
1147static struct task_struct *pick_next_task_rt(struct rq *rq)
1148{
1149 struct task_struct *p = _pick_next_task_rt(rq);
1150
1151 /* The running task is never eligible for pushing */
1152 if (p)
1153 dequeue_pushable_task(rq, p);
1154
Ingo Molnarbcf08df2008-04-19 12:11:10 +02001155#ifdef CONFIG_SMP
Gregory Haskins3f029d32009-07-29 11:08:47 -04001156 /*
1157 * We detect this state here so that we can avoid taking the RQ
1158 * lock again later if there is no need to push
1159 */
1160 rq->post_schedule = has_pushable_tasks(rq);
Ingo Molnarbcf08df2008-04-19 12:11:10 +02001161#endif
Gregory Haskins3f029d32009-07-29 11:08:47 -04001162
Peter Zijlstra6f505b12008-01-25 21:08:30 +01001163 return p;
1164}
1165
Ingo Molnar31ee5292007-08-09 11:16:49 +02001166static void put_prev_task_rt(struct rq *rq, struct task_struct *p)
Ingo Molnarbb44e5d2007-07-09 18:51:58 +02001167{
Ingo Molnarf1e14ef2007-08-09 11:16:48 +02001168 update_curr_rt(rq);
Ingo Molnarbb44e5d2007-07-09 18:51:58 +02001169 p->se.exec_start = 0;
Gregory Haskins917b6272008-12-29 09:39:53 -05001170
1171 /*
1172 * The previous task needs to be made eligible for pushing
1173 * if it is still active
1174 */
Peter Zijlstrafd2f4412011-04-05 17:23:44 +02001175 if (on_rt_rq(&p->rt) && p->rt.nr_cpus_allowed > 1)
Gregory Haskins917b6272008-12-29 09:39:53 -05001176 enqueue_pushable_task(rq, p);
Ingo Molnarbb44e5d2007-07-09 18:51:58 +02001177}
1178
Peter Williams681f3e62007-10-24 18:23:51 +02001179#ifdef CONFIG_SMP
Peter Zijlstra6f505b12008-01-25 21:08:30 +01001180
Steven Rostedte8fa1362008-01-25 21:08:05 +01001181/* Only try algorithms three times */
1182#define RT_MAX_TRIES 3
1183
Steven Rostedte8fa1362008-01-25 21:08:05 +01001184static void deactivate_task(struct rq *rq, struct task_struct *p, int sleep);
1185
Steven Rostedtf65eda42008-01-25 21:08:07 +01001186static int pick_rt_task(struct rq *rq, struct task_struct *p, int cpu)
1187{
1188 if (!task_running(rq, p) &&
Rusty Russell96f874e22008-11-25 02:35:14 +10301189 (cpu < 0 || cpumask_test_cpu(cpu, &p->cpus_allowed)) &&
Peter Zijlstra6f505b12008-01-25 21:08:30 +01001190 (p->rt.nr_cpus_allowed > 1))
Steven Rostedtf65eda42008-01-25 21:08:07 +01001191 return 1;
1192 return 0;
1193}
1194
Steven Rostedte8fa1362008-01-25 21:08:05 +01001195/* Return the second highest RT task, NULL otherwise */
Ingo Molnar79064fb2008-01-25 21:08:14 +01001196static struct task_struct *pick_next_highest_task_rt(struct rq *rq, int cpu)
Steven Rostedte8fa1362008-01-25 21:08:05 +01001197{
Peter Zijlstra6f505b12008-01-25 21:08:30 +01001198 struct task_struct *next = NULL;
1199 struct sched_rt_entity *rt_se;
1200 struct rt_prio_array *array;
1201 struct rt_rq *rt_rq;
Steven Rostedte8fa1362008-01-25 21:08:05 +01001202 int idx;
1203
Peter Zijlstra6f505b12008-01-25 21:08:30 +01001204 for_each_leaf_rt_rq(rt_rq, rq) {
1205 array = &rt_rq->active;
1206 idx = sched_find_first_bit(array->bitmap);
Peter Zijlstra49246272010-10-17 21:46:10 +02001207next_idx:
Peter Zijlstra6f505b12008-01-25 21:08:30 +01001208 if (idx >= MAX_RT_PRIO)
1209 continue;
1210 if (next && next->prio < idx)
1211 continue;
1212 list_for_each_entry(rt_se, array->queue + idx, run_list) {
Peter Zijlstra3d074672010-03-10 17:07:24 +01001213 struct task_struct *p;
1214
1215 if (!rt_entity_is_task(rt_se))
1216 continue;
1217
1218 p = rt_task_of(rt_se);
Peter Zijlstra6f505b12008-01-25 21:08:30 +01001219 if (pick_rt_task(rq, p, cpu)) {
1220 next = p;
1221 break;
1222 }
1223 }
1224 if (!next) {
1225 idx = find_next_bit(array->bitmap, MAX_RT_PRIO, idx+1);
1226 goto next_idx;
1227 }
Steven Rostedte8fa1362008-01-25 21:08:05 +01001228 }
1229
Steven Rostedte8fa1362008-01-25 21:08:05 +01001230 return next;
1231}
1232
Rusty Russell0e3900e2008-11-25 02:35:13 +10301233static DEFINE_PER_CPU(cpumask_var_t, local_cpu_mask);
Steven Rostedte8fa1362008-01-25 21:08:05 +01001234
Gregory Haskins6e1254d2008-01-25 21:08:11 +01001235static int find_lowest_rq(struct task_struct *task)
1236{
1237 struct sched_domain *sd;
Rusty Russell96f874e22008-11-25 02:35:14 +10301238 struct cpumask *lowest_mask = __get_cpu_var(local_cpu_mask);
Gregory Haskins6e1254d2008-01-25 21:08:11 +01001239 int this_cpu = smp_processor_id();
1240 int cpu = task_cpu(task);
1241
Steven Rostedt0da938c2011-06-14 18:36:25 -04001242 /* Make sure the mask is initialized first */
1243 if (unlikely(!lowest_mask))
1244 return -1;
1245
Gregory Haskins6e0534f2008-05-12 21:21:01 +02001246 if (task->rt.nr_cpus_allowed == 1)
1247 return -1; /* No other targets possible */
1248
1249 if (!cpupri_find(&task_rq(task)->rd->cpupri, task, lowest_mask))
Gregory Haskins06f90db2008-01-25 21:08:13 +01001250 return -1; /* No targets found */
1251
1252 /*
Gregory Haskins6e1254d2008-01-25 21:08:11 +01001253 * At this point we have built a mask of cpus representing the
1254 * lowest priority tasks in the system. Now we want to elect
1255 * the best one based on our affinity and topology.
1256 *
1257 * We prioritize the last cpu that the task executed on since
1258 * it is most likely cache-hot in that location.
1259 */
Rusty Russell96f874e22008-11-25 02:35:14 +10301260 if (cpumask_test_cpu(cpu, lowest_mask))
Gregory Haskins6e1254d2008-01-25 21:08:11 +01001261 return cpu;
1262
1263 /*
1264 * Otherwise, we consult the sched_domains span maps to figure
1265 * out which cpu is logically closest to our hot cache data.
1266 */
Rusty Russelle2c88062009-11-03 14:53:15 +10301267 if (!cpumask_test_cpu(this_cpu, lowest_mask))
1268 this_cpu = -1; /* Skip this_cpu opt if not among lowest */
Gregory Haskins6e1254d2008-01-25 21:08:11 +01001269
Xiaotian Fengcd4ae6a2011-04-22 18:53:54 +08001270 rcu_read_lock();
Rusty Russelle2c88062009-11-03 14:53:15 +10301271 for_each_domain(cpu, sd) {
1272 if (sd->flags & SD_WAKE_AFFINE) {
1273 int best_cpu;
Gregory Haskins6e1254d2008-01-25 21:08:11 +01001274
Rusty Russelle2c88062009-11-03 14:53:15 +10301275 /*
1276 * "this_cpu" is cheaper to preempt than a
1277 * remote processor.
1278 */
1279 if (this_cpu != -1 &&
Xiaotian Fengcd4ae6a2011-04-22 18:53:54 +08001280 cpumask_test_cpu(this_cpu, sched_domain_span(sd))) {
1281 rcu_read_unlock();
Rusty Russelle2c88062009-11-03 14:53:15 +10301282 return this_cpu;
Xiaotian Fengcd4ae6a2011-04-22 18:53:54 +08001283 }
Gregory Haskins6e1254d2008-01-25 21:08:11 +01001284
Rusty Russelle2c88062009-11-03 14:53:15 +10301285 best_cpu = cpumask_first_and(lowest_mask,
1286 sched_domain_span(sd));
Xiaotian Fengcd4ae6a2011-04-22 18:53:54 +08001287 if (best_cpu < nr_cpu_ids) {
1288 rcu_read_unlock();
Rusty Russelle2c88062009-11-03 14:53:15 +10301289 return best_cpu;
Xiaotian Fengcd4ae6a2011-04-22 18:53:54 +08001290 }
Gregory Haskins6e1254d2008-01-25 21:08:11 +01001291 }
1292 }
Xiaotian Fengcd4ae6a2011-04-22 18:53:54 +08001293 rcu_read_unlock();
Gregory Haskins6e1254d2008-01-25 21:08:11 +01001294
1295 /*
1296 * And finally, if there were no matches within the domains
1297 * just give the caller *something* to work with from the compatible
1298 * locations.
1299 */
Rusty Russelle2c88062009-11-03 14:53:15 +10301300 if (this_cpu != -1)
1301 return this_cpu;
1302
1303 cpu = cpumask_any(lowest_mask);
1304 if (cpu < nr_cpu_ids)
1305 return cpu;
1306 return -1;
Gregory Haskins07b40322008-01-25 21:08:10 +01001307}
1308
Steven Rostedte8fa1362008-01-25 21:08:05 +01001309/* Will lock the rq it finds */
Ingo Molnar4df64c02008-01-25 21:08:15 +01001310static struct rq *find_lock_lowest_rq(struct task_struct *task, struct rq *rq)
Steven Rostedte8fa1362008-01-25 21:08:05 +01001311{
1312 struct rq *lowest_rq = NULL;
Steven Rostedte8fa1362008-01-25 21:08:05 +01001313 int tries;
Ingo Molnar4df64c02008-01-25 21:08:15 +01001314 int cpu;
Steven Rostedte8fa1362008-01-25 21:08:05 +01001315
1316 for (tries = 0; tries < RT_MAX_TRIES; tries++) {
Gregory Haskins07b40322008-01-25 21:08:10 +01001317 cpu = find_lowest_rq(task);
Steven Rostedte8fa1362008-01-25 21:08:05 +01001318
Gregory Haskins2de0b462008-01-25 21:08:10 +01001319 if ((cpu == -1) || (cpu == rq->cpu))
Steven Rostedte8fa1362008-01-25 21:08:05 +01001320 break;
1321
Gregory Haskins07b40322008-01-25 21:08:10 +01001322 lowest_rq = cpu_rq(cpu);
1323
Steven Rostedte8fa1362008-01-25 21:08:05 +01001324 /* if the prio of this runqueue changed, try again */
Gregory Haskins07b40322008-01-25 21:08:10 +01001325 if (double_lock_balance(rq, lowest_rq)) {
Steven Rostedte8fa1362008-01-25 21:08:05 +01001326 /*
1327 * We had to unlock the run queue. In
1328 * the mean time, task could have
1329 * migrated already or had its affinity changed.
1330 * Also make sure that it wasn't scheduled on its rq.
1331 */
Gregory Haskins07b40322008-01-25 21:08:10 +01001332 if (unlikely(task_rq(task) != rq ||
Rusty Russell96f874e22008-11-25 02:35:14 +10301333 !cpumask_test_cpu(lowest_rq->cpu,
1334 &task->cpus_allowed) ||
Gregory Haskins07b40322008-01-25 21:08:10 +01001335 task_running(rq, task) ||
Peter Zijlstrafd2f4412011-04-05 17:23:44 +02001336 !task->on_rq)) {
Ingo Molnar4df64c02008-01-25 21:08:15 +01001337
Thomas Gleixner05fa7852009-11-17 14:28:38 +01001338 raw_spin_unlock(&lowest_rq->lock);
Steven Rostedte8fa1362008-01-25 21:08:05 +01001339 lowest_rq = NULL;
1340 break;
1341 }
1342 }
1343
1344 /* If this rq is still suitable use it. */
Gregory Haskinse864c492008-12-29 09:39:49 -05001345 if (lowest_rq->rt.highest_prio.curr > task->prio)
Steven Rostedte8fa1362008-01-25 21:08:05 +01001346 break;
1347
1348 /* try again */
Peter Zijlstra1b12bbc2008-08-11 09:30:22 +02001349 double_unlock_balance(rq, lowest_rq);
Steven Rostedte8fa1362008-01-25 21:08:05 +01001350 lowest_rq = NULL;
1351 }
1352
1353 return lowest_rq;
1354}
1355
Gregory Haskins917b6272008-12-29 09:39:53 -05001356static struct task_struct *pick_next_pushable_task(struct rq *rq)
1357{
1358 struct task_struct *p;
1359
1360 if (!has_pushable_tasks(rq))
1361 return NULL;
1362
1363 p = plist_first_entry(&rq->rt.pushable_tasks,
1364 struct task_struct, pushable_tasks);
1365
1366 BUG_ON(rq->cpu != task_cpu(p));
1367 BUG_ON(task_current(rq, p));
1368 BUG_ON(p->rt.nr_cpus_allowed <= 1);
1369
Peter Zijlstrafd2f4412011-04-05 17:23:44 +02001370 BUG_ON(!p->on_rq);
Gregory Haskins917b6272008-12-29 09:39:53 -05001371 BUG_ON(!rt_task(p));
1372
1373 return p;
1374}
1375
Steven Rostedte8fa1362008-01-25 21:08:05 +01001376/*
1377 * If the current CPU has more than one RT task, see if the non
1378 * running task can migrate over to a CPU that is running a task
1379 * of lesser priority.
1380 */
Gregory Haskins697f0a42008-01-25 21:08:09 +01001381static int push_rt_task(struct rq *rq)
Steven Rostedte8fa1362008-01-25 21:08:05 +01001382{
1383 struct task_struct *next_task;
1384 struct rq *lowest_rq;
Steven Rostedte8fa1362008-01-25 21:08:05 +01001385
Gregory Haskinsa22d7fc2008-01-25 21:08:12 +01001386 if (!rq->rt.overloaded)
1387 return 0;
1388
Gregory Haskins917b6272008-12-29 09:39:53 -05001389 next_task = pick_next_pushable_task(rq);
Steven Rostedte8fa1362008-01-25 21:08:05 +01001390 if (!next_task)
1391 return 0;
1392
Peter Zijlstra49246272010-10-17 21:46:10 +02001393retry:
Gregory Haskins697f0a42008-01-25 21:08:09 +01001394 if (unlikely(next_task == rq->curr)) {
Steven Rostedtf65eda42008-01-25 21:08:07 +01001395 WARN_ON(1);
Steven Rostedte8fa1362008-01-25 21:08:05 +01001396 return 0;
Steven Rostedtf65eda42008-01-25 21:08:07 +01001397 }
Steven Rostedte8fa1362008-01-25 21:08:05 +01001398
1399 /*
1400 * It's possible that the next_task slipped in of
1401 * higher priority than current. If that's the case
1402 * just reschedule current.
1403 */
Gregory Haskins697f0a42008-01-25 21:08:09 +01001404 if (unlikely(next_task->prio < rq->curr->prio)) {
1405 resched_task(rq->curr);
Steven Rostedte8fa1362008-01-25 21:08:05 +01001406 return 0;
1407 }
1408
Gregory Haskins697f0a42008-01-25 21:08:09 +01001409 /* We might release rq lock */
Steven Rostedte8fa1362008-01-25 21:08:05 +01001410 get_task_struct(next_task);
1411
1412 /* find_lock_lowest_rq locks the rq if found */
Gregory Haskins697f0a42008-01-25 21:08:09 +01001413 lowest_rq = find_lock_lowest_rq(next_task, rq);
Steven Rostedte8fa1362008-01-25 21:08:05 +01001414 if (!lowest_rq) {
1415 struct task_struct *task;
1416 /*
Gregory Haskins697f0a42008-01-25 21:08:09 +01001417 * find lock_lowest_rq releases rq->lock
Gregory Haskins15635132008-12-29 09:39:53 -05001418 * so it is possible that next_task has migrated.
1419 *
1420 * We need to make sure that the task is still on the same
1421 * run-queue and is also still the next task eligible for
1422 * pushing.
Steven Rostedte8fa1362008-01-25 21:08:05 +01001423 */
Gregory Haskins917b6272008-12-29 09:39:53 -05001424 task = pick_next_pushable_task(rq);
Gregory Haskins15635132008-12-29 09:39:53 -05001425 if (task_cpu(next_task) == rq->cpu && task == next_task) {
1426 /*
Lucas De Marchi25985ed2011-03-30 22:57:33 -03001427 * If we get here, the task hasn't moved at all, but
Gregory Haskins15635132008-12-29 09:39:53 -05001428 * it has failed to push. We will not try again,
1429 * since the other cpus will pull from us when they
1430 * are ready.
1431 */
1432 dequeue_pushable_task(rq, next_task);
1433 goto out;
Steven Rostedte8fa1362008-01-25 21:08:05 +01001434 }
Gregory Haskins917b6272008-12-29 09:39:53 -05001435
Gregory Haskins15635132008-12-29 09:39:53 -05001436 if (!task)
1437 /* No more tasks, just exit */
1438 goto out;
1439
Gregory Haskins917b6272008-12-29 09:39:53 -05001440 /*
Gregory Haskins15635132008-12-29 09:39:53 -05001441 * Something has shifted, try again.
Gregory Haskins917b6272008-12-29 09:39:53 -05001442 */
Gregory Haskins15635132008-12-29 09:39:53 -05001443 put_task_struct(next_task);
1444 next_task = task;
1445 goto retry;
Steven Rostedte8fa1362008-01-25 21:08:05 +01001446 }
1447
Gregory Haskins697f0a42008-01-25 21:08:09 +01001448 deactivate_task(rq, next_task, 0);
Steven Rostedte8fa1362008-01-25 21:08:05 +01001449 set_task_cpu(next_task, lowest_rq->cpu);
1450 activate_task(lowest_rq, next_task, 0);
1451
1452 resched_task(lowest_rq->curr);
1453
Peter Zijlstra1b12bbc2008-08-11 09:30:22 +02001454 double_unlock_balance(rq, lowest_rq);
Steven Rostedte8fa1362008-01-25 21:08:05 +01001455
Steven Rostedte8fa1362008-01-25 21:08:05 +01001456out:
1457 put_task_struct(next_task);
1458
Gregory Haskins917b6272008-12-29 09:39:53 -05001459 return 1;
Steven Rostedte8fa1362008-01-25 21:08:05 +01001460}
1461
Steven Rostedte8fa1362008-01-25 21:08:05 +01001462static void push_rt_tasks(struct rq *rq)
1463{
1464 /* push_rt_task will return true if it moved an RT */
1465 while (push_rt_task(rq))
1466 ;
1467}
1468
Steven Rostedtf65eda42008-01-25 21:08:07 +01001469static int pull_rt_task(struct rq *this_rq)
1470{
Ingo Molnar80bf3172008-01-25 21:08:17 +01001471 int this_cpu = this_rq->cpu, ret = 0, cpu;
Gregory Haskinsa8728942008-12-29 09:39:49 -05001472 struct task_struct *p;
Steven Rostedtf65eda42008-01-25 21:08:07 +01001473 struct rq *src_rq;
Steven Rostedtf65eda42008-01-25 21:08:07 +01001474
Gregory Haskins637f5082008-01-25 21:08:18 +01001475 if (likely(!rt_overloaded(this_rq)))
Steven Rostedtf65eda42008-01-25 21:08:07 +01001476 return 0;
1477
Rusty Russellc6c49272008-11-25 02:35:05 +10301478 for_each_cpu(cpu, this_rq->rd->rto_mask) {
Steven Rostedtf65eda42008-01-25 21:08:07 +01001479 if (this_cpu == cpu)
1480 continue;
1481
1482 src_rq = cpu_rq(cpu);
Gregory Haskins74ab8e42008-12-29 09:39:50 -05001483
1484 /*
1485 * Don't bother taking the src_rq->lock if the next highest
1486 * task is known to be lower-priority than our current task.
1487 * This may look racy, but if this value is about to go
1488 * logically higher, the src_rq will push this task away.
1489 * And if its going logically lower, we do not care
1490 */
1491 if (src_rq->rt.highest_prio.next >=
1492 this_rq->rt.highest_prio.curr)
1493 continue;
1494
Steven Rostedtf65eda42008-01-25 21:08:07 +01001495 /*
1496 * We can potentially drop this_rq's lock in
1497 * double_lock_balance, and another CPU could
Gregory Haskinsa8728942008-12-29 09:39:49 -05001498 * alter this_rq
Steven Rostedtf65eda42008-01-25 21:08:07 +01001499 */
Gregory Haskinsa8728942008-12-29 09:39:49 -05001500 double_lock_balance(this_rq, src_rq);
Steven Rostedtf65eda42008-01-25 21:08:07 +01001501
1502 /*
1503 * Are there still pullable RT tasks?
1504 */
Mike Galbraith614ee1f2008-01-25 21:08:30 +01001505 if (src_rq->rt.rt_nr_running <= 1)
1506 goto skip;
Steven Rostedtf65eda42008-01-25 21:08:07 +01001507
Steven Rostedtf65eda42008-01-25 21:08:07 +01001508 p = pick_next_highest_task_rt(src_rq, this_cpu);
1509
1510 /*
1511 * Do we have an RT task that preempts
1512 * the to-be-scheduled task?
1513 */
Gregory Haskinsa8728942008-12-29 09:39:49 -05001514 if (p && (p->prio < this_rq->rt.highest_prio.curr)) {
Steven Rostedtf65eda42008-01-25 21:08:07 +01001515 WARN_ON(p == src_rq->curr);
Peter Zijlstrafd2f4412011-04-05 17:23:44 +02001516 WARN_ON(!p->on_rq);
Steven Rostedtf65eda42008-01-25 21:08:07 +01001517
1518 /*
1519 * There's a chance that p is higher in priority
1520 * than what's currently running on its cpu.
1521 * This is just that p is wakeing up and hasn't
1522 * had a chance to schedule. We only pull
1523 * p if it is lower in priority than the
Gregory Haskinsa8728942008-12-29 09:39:49 -05001524 * current task on the run queue
Steven Rostedtf65eda42008-01-25 21:08:07 +01001525 */
Gregory Haskinsa8728942008-12-29 09:39:49 -05001526 if (p->prio < src_rq->curr->prio)
Mike Galbraith614ee1f2008-01-25 21:08:30 +01001527 goto skip;
Steven Rostedtf65eda42008-01-25 21:08:07 +01001528
1529 ret = 1;
1530
1531 deactivate_task(src_rq, p, 0);
1532 set_task_cpu(p, this_cpu);
1533 activate_task(this_rq, p, 0);
1534 /*
1535 * We continue with the search, just in
1536 * case there's an even higher prio task
Lucas De Marchi25985ed2011-03-30 22:57:33 -03001537 * in another runqueue. (low likelihood
Steven Rostedtf65eda42008-01-25 21:08:07 +01001538 * but possible)
Steven Rostedtf65eda42008-01-25 21:08:07 +01001539 */
Steven Rostedtf65eda42008-01-25 21:08:07 +01001540 }
Peter Zijlstra49246272010-10-17 21:46:10 +02001541skip:
Peter Zijlstra1b12bbc2008-08-11 09:30:22 +02001542 double_unlock_balance(this_rq, src_rq);
Steven Rostedtf65eda42008-01-25 21:08:07 +01001543 }
1544
1545 return ret;
1546}
1547
Steven Rostedt9a897c52008-01-25 21:08:22 +01001548static void pre_schedule_rt(struct rq *rq, struct task_struct *prev)
Steven Rostedtf65eda42008-01-25 21:08:07 +01001549{
1550 /* Try to pull RT tasks here if we lower this rq's prio */
Gregory Haskinse864c492008-12-29 09:39:49 -05001551 if (unlikely(rt_task(prev)) && rq->rt.highest_prio.curr > prev->prio)
Steven Rostedtf65eda42008-01-25 21:08:07 +01001552 pull_rt_task(rq);
1553}
1554
Steven Rostedt9a897c52008-01-25 21:08:22 +01001555static void post_schedule_rt(struct rq *rq)
Steven Rostedte8fa1362008-01-25 21:08:05 +01001556{
Gregory Haskins967fc042008-12-29 09:39:52 -05001557 push_rt_tasks(rq);
Steven Rostedte8fa1362008-01-25 21:08:05 +01001558}
1559
Gregory Haskins8ae121a2008-04-23 07:13:29 -04001560/*
1561 * If we are not running and we are not going to reschedule soon, we should
1562 * try to push tasks away now
1563 */
Peter Zijlstraefbbd052009-12-16 18:04:40 +01001564static void task_woken_rt(struct rq *rq, struct task_struct *p)
Steven Rostedt4642daf2008-01-25 21:08:07 +01001565{
Steven Rostedt9a897c52008-01-25 21:08:22 +01001566 if (!task_running(rq, p) &&
Gregory Haskins8ae121a2008-04-23 07:13:29 -04001567 !test_tsk_need_resched(rq->curr) &&
Gregory Haskins917b6272008-12-29 09:39:53 -05001568 has_pushable_tasks(rq) &&
Steven Rostedtb3bc2112010-09-20 22:40:04 -04001569 p->rt.nr_cpus_allowed > 1 &&
Steven Rostedt43fa5462010-09-20 22:40:03 -04001570 rt_task(rq->curr) &&
Steven Rostedtb3bc2112010-09-20 22:40:04 -04001571 (rq->curr->rt.nr_cpus_allowed < 2 ||
1572 rq->curr->prio < p->prio))
Steven Rostedt4642daf2008-01-25 21:08:07 +01001573 push_rt_tasks(rq);
1574}
1575
Mike Traviscd8ba7c2008-03-26 14:23:49 -07001576static void set_cpus_allowed_rt(struct task_struct *p,
Rusty Russell96f874e22008-11-25 02:35:14 +10301577 const struct cpumask *new_mask)
Gregory Haskins73fe6aa2008-01-25 21:08:07 +01001578{
Rusty Russell96f874e22008-11-25 02:35:14 +10301579 int weight = cpumask_weight(new_mask);
Gregory Haskins73fe6aa2008-01-25 21:08:07 +01001580
1581 BUG_ON(!rt_task(p));
1582
1583 /*
1584 * Update the migration status of the RQ if we have an RT task
1585 * which is running AND changing its weight value.
1586 */
Peter Zijlstrafd2f4412011-04-05 17:23:44 +02001587 if (p->on_rq && (weight != p->rt.nr_cpus_allowed)) {
Gregory Haskins73fe6aa2008-01-25 21:08:07 +01001588 struct rq *rq = task_rq(p);
1589
Gregory Haskins917b6272008-12-29 09:39:53 -05001590 if (!task_current(rq, p)) {
1591 /*
1592 * Make sure we dequeue this task from the pushable list
1593 * before going further. It will either remain off of
1594 * the list because we are no longer pushable, or it
1595 * will be requeued.
1596 */
1597 if (p->rt.nr_cpus_allowed > 1)
1598 dequeue_pushable_task(rq, p);
1599
1600 /*
1601 * Requeue if our weight is changing and still > 1
1602 */
1603 if (weight > 1)
1604 enqueue_pushable_task(rq, p);
1605
1606 }
1607
Peter Zijlstra6f505b12008-01-25 21:08:30 +01001608 if ((p->rt.nr_cpus_allowed <= 1) && (weight > 1)) {
Gregory Haskins73fe6aa2008-01-25 21:08:07 +01001609 rq->rt.rt_nr_migratory++;
Peter Zijlstra6f505b12008-01-25 21:08:30 +01001610 } else if ((p->rt.nr_cpus_allowed > 1) && (weight <= 1)) {
Gregory Haskins73fe6aa2008-01-25 21:08:07 +01001611 BUG_ON(!rq->rt.rt_nr_migratory);
1612 rq->rt.rt_nr_migratory--;
1613 }
1614
Gregory Haskins398a1532009-01-14 09:10:04 -05001615 update_rt_migration(&rq->rt);
Gregory Haskins73fe6aa2008-01-25 21:08:07 +01001616 }
1617
Rusty Russell96f874e22008-11-25 02:35:14 +10301618 cpumask_copy(&p->cpus_allowed, new_mask);
Peter Zijlstra6f505b12008-01-25 21:08:30 +01001619 p->rt.nr_cpus_allowed = weight;
Gregory Haskins73fe6aa2008-01-25 21:08:07 +01001620}
Ingo Molnardeeeccd2008-01-25 21:08:15 +01001621
Ingo Molnarbdd7c812008-01-25 21:08:18 +01001622/* Assumes rq->lock is held */
Gregory Haskins1f11eb6a2008-06-04 15:04:05 -04001623static void rq_online_rt(struct rq *rq)
Ingo Molnarbdd7c812008-01-25 21:08:18 +01001624{
1625 if (rq->rt.overloaded)
1626 rt_set_overload(rq);
Gregory Haskins6e0534f2008-05-12 21:21:01 +02001627
Peter Zijlstra7def2be2008-06-05 14:49:58 +02001628 __enable_runtime(rq);
1629
Gregory Haskinse864c492008-12-29 09:39:49 -05001630 cpupri_set(&rq->rd->cpupri, rq->cpu, rq->rt.highest_prio.curr);
Ingo Molnarbdd7c812008-01-25 21:08:18 +01001631}
1632
1633/* Assumes rq->lock is held */
Gregory Haskins1f11eb6a2008-06-04 15:04:05 -04001634static void rq_offline_rt(struct rq *rq)
Ingo Molnarbdd7c812008-01-25 21:08:18 +01001635{
1636 if (rq->rt.overloaded)
1637 rt_clear_overload(rq);
Gregory Haskins6e0534f2008-05-12 21:21:01 +02001638
Peter Zijlstra7def2be2008-06-05 14:49:58 +02001639 __disable_runtime(rq);
1640
Gregory Haskins6e0534f2008-05-12 21:21:01 +02001641 cpupri_set(&rq->rd->cpupri, rq->cpu, CPUPRI_INVALID);
Ingo Molnarbdd7c812008-01-25 21:08:18 +01001642}
Steven Rostedtcb469842008-01-25 21:08:22 +01001643
1644/*
1645 * When switch from the rt queue, we bring ourselves to a position
1646 * that we might want to pull RT tasks from other runqueues.
1647 */
Peter Zijlstrada7a7352011-01-17 17:03:27 +01001648static void switched_from_rt(struct rq *rq, struct task_struct *p)
Steven Rostedtcb469842008-01-25 21:08:22 +01001649{
1650 /*
1651 * If there are other RT tasks then we will reschedule
1652 * and the scheduling of the other RT tasks will handle
1653 * the balancing. But if we are the last RT task
1654 * we may need to handle the pulling of RT tasks
1655 * now.
1656 */
Peter Zijlstrafd2f4412011-04-05 17:23:44 +02001657 if (p->on_rq && !rq->rt.rt_nr_running)
Steven Rostedtcb469842008-01-25 21:08:22 +01001658 pull_rt_task(rq);
1659}
Rusty Russell3d8cbdf2008-11-25 09:58:41 +10301660
1661static inline void init_sched_rt_class(void)
1662{
1663 unsigned int i;
1664
1665 for_each_possible_cpu(i)
Yinghai Lueaa95842009-06-06 14:51:36 -07001666 zalloc_cpumask_var_node(&per_cpu(local_cpu_mask, i),
Mike Travis6ca09df2008-12-31 18:08:45 -08001667 GFP_KERNEL, cpu_to_node(i));
Rusty Russell3d8cbdf2008-11-25 09:58:41 +10301668}
Steven Rostedte8fa1362008-01-25 21:08:05 +01001669#endif /* CONFIG_SMP */
Ingo Molnarbb44e5d2007-07-09 18:51:58 +02001670
Steven Rostedtcb469842008-01-25 21:08:22 +01001671/*
1672 * When switching a task to RT, we may overload the runqueue
1673 * with RT tasks. In this case we try to push them off to
1674 * other runqueues.
1675 */
Peter Zijlstrada7a7352011-01-17 17:03:27 +01001676static void switched_to_rt(struct rq *rq, struct task_struct *p)
Steven Rostedtcb469842008-01-25 21:08:22 +01001677{
1678 int check_resched = 1;
1679
1680 /*
1681 * If we are already running, then there's nothing
1682 * that needs to be done. But if we are not running
1683 * we may need to preempt the current running task.
1684 * If that current running task is also an RT task
1685 * then see if we can move to another run queue.
1686 */
Peter Zijlstrafd2f4412011-04-05 17:23:44 +02001687 if (p->on_rq && rq->curr != p) {
Steven Rostedtcb469842008-01-25 21:08:22 +01001688#ifdef CONFIG_SMP
1689 if (rq->rt.overloaded && push_rt_task(rq) &&
1690 /* Don't resched if we changed runqueues */
1691 rq != task_rq(p))
1692 check_resched = 0;
1693#endif /* CONFIG_SMP */
1694 if (check_resched && p->prio < rq->curr->prio)
1695 resched_task(rq->curr);
1696 }
1697}
1698
1699/*
1700 * Priority of the task has changed. This may cause
1701 * us to initiate a push or pull.
1702 */
Peter Zijlstrada7a7352011-01-17 17:03:27 +01001703static void
1704prio_changed_rt(struct rq *rq, struct task_struct *p, int oldprio)
Steven Rostedtcb469842008-01-25 21:08:22 +01001705{
Peter Zijlstrafd2f4412011-04-05 17:23:44 +02001706 if (!p->on_rq)
Peter Zijlstrada7a7352011-01-17 17:03:27 +01001707 return;
1708
1709 if (rq->curr == p) {
Steven Rostedtcb469842008-01-25 21:08:22 +01001710#ifdef CONFIG_SMP
1711 /*
1712 * If our priority decreases while running, we
1713 * may need to pull tasks to this runqueue.
1714 */
1715 if (oldprio < p->prio)
1716 pull_rt_task(rq);
1717 /*
1718 * If there's a higher priority task waiting to run
Steven Rostedt6fa46fa2008-03-05 10:00:12 -05001719 * then reschedule. Note, the above pull_rt_task
1720 * can release the rq lock and p could migrate.
1721 * Only reschedule if p is still on the same runqueue.
Steven Rostedtcb469842008-01-25 21:08:22 +01001722 */
Gregory Haskinse864c492008-12-29 09:39:49 -05001723 if (p->prio > rq->rt.highest_prio.curr && rq->curr == p)
Steven Rostedtcb469842008-01-25 21:08:22 +01001724 resched_task(p);
1725#else
1726 /* For UP simply resched on drop of prio */
1727 if (oldprio < p->prio)
1728 resched_task(p);
1729#endif /* CONFIG_SMP */
1730 } else {
1731 /*
1732 * This task is not running, but if it is
1733 * greater than the current running task
1734 * then reschedule.
1735 */
1736 if (p->prio < rq->curr->prio)
1737 resched_task(rq->curr);
1738 }
1739}
1740
Peter Zijlstra78f2c7d2008-01-25 21:08:27 +01001741static void watchdog(struct rq *rq, struct task_struct *p)
1742{
1743 unsigned long soft, hard;
1744
Jiri Slaby78d7d402010-03-05 13:42:54 -08001745 /* max may change after cur was read, this will be fixed next tick */
1746 soft = task_rlimit(p, RLIMIT_RTTIME);
1747 hard = task_rlimit_max(p, RLIMIT_RTTIME);
Peter Zijlstra78f2c7d2008-01-25 21:08:27 +01001748
1749 if (soft != RLIM_INFINITY) {
1750 unsigned long next;
1751
1752 p->rt.timeout++;
1753 next = DIV_ROUND_UP(min(soft, hard), USEC_PER_SEC/HZ);
Peter Zijlstra5a52dd52008-01-25 21:08:32 +01001754 if (p->rt.timeout > next)
Frank Mayharf06febc2008-09-12 09:54:39 -07001755 p->cputime_expires.sched_exp = p->se.sum_exec_runtime;
Peter Zijlstra78f2c7d2008-01-25 21:08:27 +01001756 }
1757}
Steven Rostedtcb469842008-01-25 21:08:22 +01001758
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +01001759static void task_tick_rt(struct rq *rq, struct task_struct *p, int queued)
Ingo Molnarbb44e5d2007-07-09 18:51:58 +02001760{
Peter Zijlstra67e2be02007-12-20 15:01:17 +01001761 update_curr_rt(rq);
1762
Peter Zijlstra78f2c7d2008-01-25 21:08:27 +01001763 watchdog(rq, p);
1764
Ingo Molnarbb44e5d2007-07-09 18:51:58 +02001765 /*
1766 * RR tasks need a special form of timeslice management.
1767 * FIFO tasks have no timeslices.
1768 */
1769 if (p->policy != SCHED_RR)
1770 return;
1771
Peter Zijlstrafa717062008-01-25 21:08:27 +01001772 if (--p->rt.time_slice)
Ingo Molnarbb44e5d2007-07-09 18:51:58 +02001773 return;
1774
Peter Zijlstrafa717062008-01-25 21:08:27 +01001775 p->rt.time_slice = DEF_TIMESLICE;
Ingo Molnarbb44e5d2007-07-09 18:51:58 +02001776
Dmitry Adamushko98fbc792007-08-24 20:39:10 +02001777 /*
1778 * Requeue to the end of queue if we are not the only element
1779 * on the queue:
1780 */
Peter Zijlstrafa717062008-01-25 21:08:27 +01001781 if (p->rt.run_list.prev != p->rt.run_list.next) {
Dmitry Adamushko7ebefa82008-07-01 23:32:15 +02001782 requeue_task_rt(rq, p, 0);
Dmitry Adamushko98fbc792007-08-24 20:39:10 +02001783 set_tsk_need_resched(p);
1784 }
Ingo Molnarbb44e5d2007-07-09 18:51:58 +02001785}
1786
Srivatsa Vaddagiri83b699e2007-10-15 17:00:08 +02001787static void set_curr_task_rt(struct rq *rq)
1788{
1789 struct task_struct *p = rq->curr;
1790
Venkatesh Pallipadi305e6832010-10-04 17:03:21 -07001791 p->se.exec_start = rq->clock_task;
Gregory Haskins917b6272008-12-29 09:39:53 -05001792
1793 /* The running task is never eligible for pushing */
1794 dequeue_pushable_task(rq, p);
Srivatsa Vaddagiri83b699e2007-10-15 17:00:08 +02001795}
1796
H Hartley Sweeten6d686f42010-01-13 20:21:52 -07001797static unsigned int get_rr_interval_rt(struct rq *rq, struct task_struct *task)
Peter Williams0d721ce2009-09-21 01:31:53 +00001798{
1799 /*
1800 * Time slice is 0 for SCHED_FIFO tasks
1801 */
1802 if (task->policy == SCHED_RR)
1803 return DEF_TIMESLICE;
1804 else
1805 return 0;
1806}
1807
Harvey Harrison2abdad02008-04-25 10:53:13 -07001808static const struct sched_class rt_sched_class = {
Ingo Molnar5522d5d2007-10-15 17:00:12 +02001809 .next = &fair_sched_class,
Ingo Molnarbb44e5d2007-07-09 18:51:58 +02001810 .enqueue_task = enqueue_task_rt,
1811 .dequeue_task = dequeue_task_rt,
1812 .yield_task = yield_task_rt,
1813
1814 .check_preempt_curr = check_preempt_curr_rt,
1815
1816 .pick_next_task = pick_next_task_rt,
1817 .put_prev_task = put_prev_task_rt,
1818
Peter Williams681f3e62007-10-24 18:23:51 +02001819#ifdef CONFIG_SMP
Li Zefan4ce72a22008-10-22 15:25:26 +08001820 .select_task_rq = select_task_rq_rt,
1821
Gregory Haskins73fe6aa2008-01-25 21:08:07 +01001822 .set_cpus_allowed = set_cpus_allowed_rt,
Gregory Haskins1f11eb6a2008-06-04 15:04:05 -04001823 .rq_online = rq_online_rt,
1824 .rq_offline = rq_offline_rt,
Steven Rostedt9a897c52008-01-25 21:08:22 +01001825 .pre_schedule = pre_schedule_rt,
1826 .post_schedule = post_schedule_rt,
Peter Zijlstraefbbd052009-12-16 18:04:40 +01001827 .task_woken = task_woken_rt,
Steven Rostedtcb469842008-01-25 21:08:22 +01001828 .switched_from = switched_from_rt,
Peter Williams681f3e62007-10-24 18:23:51 +02001829#endif
Ingo Molnarbb44e5d2007-07-09 18:51:58 +02001830
Srivatsa Vaddagiri83b699e2007-10-15 17:00:08 +02001831 .set_curr_task = set_curr_task_rt,
Ingo Molnarbb44e5d2007-07-09 18:51:58 +02001832 .task_tick = task_tick_rt,
Steven Rostedtcb469842008-01-25 21:08:22 +01001833
Peter Williams0d721ce2009-09-21 01:31:53 +00001834 .get_rr_interval = get_rr_interval_rt,
1835
Steven Rostedtcb469842008-01-25 21:08:22 +01001836 .prio_changed = prio_changed_rt,
1837 .switched_to = switched_to_rt,
Ingo Molnarbb44e5d2007-07-09 18:51:58 +02001838};
Peter Zijlstraada18de2008-06-19 14:22:24 +02001839
1840#ifdef CONFIG_SCHED_DEBUG
1841extern void print_rt_rq(struct seq_file *m, int cpu, struct rt_rq *rt_rq);
1842
1843static void print_rt_stats(struct seq_file *m, int cpu)
1844{
Cheng Xuec514c42011-05-14 14:20:02 +08001845 rt_rq_iter_t iter;
Peter Zijlstraada18de2008-06-19 14:22:24 +02001846 struct rt_rq *rt_rq;
1847
1848 rcu_read_lock();
Cheng Xuec514c42011-05-14 14:20:02 +08001849 for_each_rt_rq(rt_rq, iter, cpu_rq(cpu))
Peter Zijlstraada18de2008-06-19 14:22:24 +02001850 print_rt_rq(m, cpu, rt_rq);
1851 rcu_read_unlock();
1852}
Dhaval Giani55e12e52008-06-24 23:39:43 +05301853#endif /* CONFIG_SCHED_DEBUG */
Rusty Russell0e3900e2008-11-25 02:35:13 +10301854