sched debug: remove the 'u64 now' parameter from print_task()/_rq()
[deliverable/linux.git] / kernel / sched.c
CommitLineData
1da177e4
LT
1/*
2 * kernel/sched.c
3 *
4 * Kernel scheduler and related syscalls
5 *
6 * Copyright (C) 1991-2002 Linus Torvalds
7 *
8 * 1996-12-23 Modified by Dave Grothe to fix bugs in semaphores and
9 * make semaphores SMP safe
10 * 1998-11-19 Implemented schedule_timeout() and related stuff
11 * by Andrea Arcangeli
12 * 2002-01-04 New ultra-scalable O(1) scheduler by Ingo Molnar:
13 * hybrid priority-list and round-robin design with
14 * an array-switch method of distributing timeslices
15 * and per-CPU runqueues. Cleanups and useful suggestions
16 * by Davide Libenzi, preemptible kernel bits by Robert Love.
17 * 2003-09-03 Interactivity tuning by Con Kolivas.
18 * 2004-04-02 Scheduler domains code by Nick Piggin
c31f2e8a
IM
19 * 2007-04-15 Work begun on replacing all interactivity tuning with a
20 * fair scheduling design by Con Kolivas.
21 * 2007-05-05 Load balancing (smp-nice) and other improvements
22 * by Peter Williams
23 * 2007-05-06 Interactivity improvements to CFS by Mike Galbraith
24 * 2007-07-01 Group scheduling enhancements by Srivatsa Vaddagiri
1da177e4
LT
25 */
26
27#include <linux/mm.h>
28#include <linux/module.h>
29#include <linux/nmi.h>
30#include <linux/init.h>
dff06c15 31#include <linux/uaccess.h>
1da177e4
LT
32#include <linux/highmem.h>
33#include <linux/smp_lock.h>
34#include <asm/mmu_context.h>
35#include <linux/interrupt.h>
c59ede7b 36#include <linux/capability.h>
1da177e4
LT
37#include <linux/completion.h>
38#include <linux/kernel_stat.h>
9a11b49a 39#include <linux/debug_locks.h>
1da177e4
LT
40#include <linux/security.h>
41#include <linux/notifier.h>
42#include <linux/profile.h>
7dfb7103 43#include <linux/freezer.h>
198e2f18 44#include <linux/vmalloc.h>
1da177e4
LT
45#include <linux/blkdev.h>
46#include <linux/delay.h>
47#include <linux/smp.h>
48#include <linux/threads.h>
49#include <linux/timer.h>
50#include <linux/rcupdate.h>
51#include <linux/cpu.h>
52#include <linux/cpuset.h>
53#include <linux/percpu.h>
54#include <linux/kthread.h>
55#include <linux/seq_file.h>
e692ab53 56#include <linux/sysctl.h>
1da177e4
LT
57#include <linux/syscalls.h>
58#include <linux/times.h>
8f0ab514 59#include <linux/tsacct_kern.h>
c6fd91f0 60#include <linux/kprobes.h>
0ff92245 61#include <linux/delayacct.h>
5517d86b 62#include <linux/reciprocal_div.h>
dff06c15 63#include <linux/unistd.h>
1da177e4 64
5517d86b 65#include <asm/tlb.h>
1da177e4 66
b035b6de
AD
67/*
68 * Scheduler clock - returns current time in nanosec units.
69 * This is default implementation.
70 * Architectures and sub-architectures can override this.
71 */
72unsigned long long __attribute__((weak)) sched_clock(void)
73{
74 return (unsigned long long)jiffies * (1000000000 / HZ);
75}
76
1da177e4
LT
77/*
78 * Convert user-nice values [ -20 ... 0 ... 19 ]
79 * to static priority [ MAX_RT_PRIO..MAX_PRIO-1 ],
80 * and back.
81 */
82#define NICE_TO_PRIO(nice) (MAX_RT_PRIO + (nice) + 20)
83#define PRIO_TO_NICE(prio) ((prio) - MAX_RT_PRIO - 20)
84#define TASK_NICE(p) PRIO_TO_NICE((p)->static_prio)
85
86/*
87 * 'User priority' is the nice value converted to something we
88 * can work with better when scaling various scheduler parameters,
89 * it's a [ 0 ... 39 ] range.
90 */
91#define USER_PRIO(p) ((p)-MAX_RT_PRIO)
92#define TASK_USER_PRIO(p) USER_PRIO((p)->static_prio)
93#define MAX_USER_PRIO (USER_PRIO(MAX_PRIO))
94
95/*
96 * Some helpers for converting nanosecond timing to jiffy resolution
97 */
98#define NS_TO_JIFFIES(TIME) ((TIME) / (1000000000 / HZ))
99#define JIFFIES_TO_NS(TIME) ((TIME) * (1000000000 / HZ))
100
6aa645ea
IM
101#define NICE_0_LOAD SCHED_LOAD_SCALE
102#define NICE_0_SHIFT SCHED_LOAD_SHIFT
103
1da177e4
LT
104/*
105 * These are the 'tuning knobs' of the scheduler:
106 *
107 * Minimum timeslice is 5 msecs (or 1 jiffy, whichever is larger),
108 * default timeslice is 100 msecs, maximum timeslice is 800 msecs.
109 * Timeslices get refilled after they expire.
110 */
111#define MIN_TIMESLICE max(5 * HZ / 1000, 1)
112#define DEF_TIMESLICE (100 * HZ / 1000)
2dd73a4f 113
5517d86b
ED
114#ifdef CONFIG_SMP
115/*
116 * Divide a load by a sched group cpu_power : (load / sg->__cpu_power)
117 * Since cpu_power is a 'constant', we can use a reciprocal divide.
118 */
119static inline u32 sg_div_cpu_power(const struct sched_group *sg, u32 load)
120{
121 return reciprocal_divide(load, sg->reciprocal_cpu_power);
122}
123
124/*
125 * Each time a sched group cpu_power is changed,
126 * we must compute its reciprocal value
127 */
128static inline void sg_inc_cpu_power(struct sched_group *sg, u32 val)
129{
130 sg->__cpu_power += val;
131 sg->reciprocal_cpu_power = reciprocal_value(sg->__cpu_power);
132}
133#endif
134
634fa8c9
IM
135#define SCALE_PRIO(x, prio) \
136 max(x * (MAX_PRIO - prio) / (MAX_USER_PRIO / 2), MIN_TIMESLICE)
137
91fcdd4e 138/*
634fa8c9 139 * static_prio_timeslice() scales user-nice values [ -20 ... 0 ... 19 ]
91fcdd4e 140 * to time slice values: [800ms ... 100ms ... 5ms]
91fcdd4e 141 */
634fa8c9 142static unsigned int static_prio_timeslice(int static_prio)
2dd73a4f 143{
634fa8c9
IM
144 if (static_prio == NICE_TO_PRIO(19))
145 return 1;
146
147 if (static_prio < NICE_TO_PRIO(0))
148 return SCALE_PRIO(DEF_TIMESLICE * 4, static_prio);
149 else
150 return SCALE_PRIO(DEF_TIMESLICE, static_prio);
2dd73a4f
PW
151}
152
e05606d3
IM
153static inline int rt_policy(int policy)
154{
155 if (unlikely(policy == SCHED_FIFO) || unlikely(policy == SCHED_RR))
156 return 1;
157 return 0;
158}
159
160static inline int task_has_rt_policy(struct task_struct *p)
161{
162 return rt_policy(p->policy);
163}
164
1da177e4 165/*
6aa645ea 166 * This is the priority-queue data structure of the RT scheduling class:
1da177e4 167 */
6aa645ea
IM
168struct rt_prio_array {
169 DECLARE_BITMAP(bitmap, MAX_RT_PRIO+1); /* include 1 bit for delimiter */
170 struct list_head queue[MAX_RT_PRIO];
171};
172
173struct load_stat {
174 struct load_weight load;
175 u64 load_update_start, load_update_last;
176 unsigned long delta_fair, delta_exec, delta_stat;
177};
178
179/* CFS-related fields in a runqueue */
180struct cfs_rq {
181 struct load_weight load;
182 unsigned long nr_running;
183
184 s64 fair_clock;
185 u64 exec_clock;
186 s64 wait_runtime;
187 u64 sleeper_bonus;
188 unsigned long wait_runtime_overruns, wait_runtime_underruns;
189
190 struct rb_root tasks_timeline;
191 struct rb_node *rb_leftmost;
192 struct rb_node *rb_load_balance_curr;
193#ifdef CONFIG_FAIR_GROUP_SCHED
194 /* 'curr' points to currently running entity on this cfs_rq.
195 * It is set to NULL otherwise (i.e when none are currently running).
196 */
197 struct sched_entity *curr;
198 struct rq *rq; /* cpu runqueue to which this cfs_rq is attached */
199
200 /* leaf cfs_rqs are those that hold tasks (lowest schedulable entity in
201 * a hierarchy). Non-leaf lrqs hold other higher schedulable entities
202 * (like users, containers etc.)
203 *
204 * leaf_cfs_rq_list ties together list of leaf cfs_rq's in a cpu. This
205 * list is used during load balance.
206 */
207 struct list_head leaf_cfs_rq_list; /* Better name : task_cfs_rq_list? */
208#endif
209};
1da177e4 210
6aa645ea
IM
211/* Real-Time classes' related field in a runqueue: */
212struct rt_rq {
213 struct rt_prio_array active;
214 int rt_load_balance_idx;
215 struct list_head *rt_load_balance_head, *rt_load_balance_curr;
216};
217
1da177e4
LT
218/*
219 * This is the main, per-CPU runqueue data structure.
220 *
221 * Locking rule: those places that want to lock multiple runqueues
222 * (such as the load balancing or the thread migration code), lock
223 * acquire operations must be ordered by ascending &runqueue.
224 */
70b97a7f 225struct rq {
6aa645ea 226 spinlock_t lock; /* runqueue lock */
1da177e4
LT
227
228 /*
229 * nr_running and cpu_load should be in the same cacheline because
230 * remote CPUs use both these fields when doing load calculation.
231 */
232 unsigned long nr_running;
6aa645ea
IM
233 #define CPU_LOAD_IDX_MAX 5
234 unsigned long cpu_load[CPU_LOAD_IDX_MAX];
bdecea3a 235 unsigned char idle_at_tick;
46cb4b7c
SS
236#ifdef CONFIG_NO_HZ
237 unsigned char in_nohz_recently;
238#endif
6aa645ea
IM
239 struct load_stat ls; /* capture load from *all* tasks on this cpu */
240 unsigned long nr_load_updates;
241 u64 nr_switches;
242
243 struct cfs_rq cfs;
244#ifdef CONFIG_FAIR_GROUP_SCHED
245 struct list_head leaf_cfs_rq_list; /* list of leaf cfs_rq on this cpu */
1da177e4 246#endif
6aa645ea 247 struct rt_rq rt;
1da177e4
LT
248
249 /*
250 * This is part of a global counter where only the total sum
251 * over all CPUs matters. A task can increase this counter on
252 * one CPU and if it got migrated afterwards it may decrease
253 * it on another CPU. Always updated under the runqueue lock:
254 */
255 unsigned long nr_uninterruptible;
256
36c8b586 257 struct task_struct *curr, *idle;
c9819f45 258 unsigned long next_balance;
1da177e4 259 struct mm_struct *prev_mm;
6aa645ea 260
6aa645ea
IM
261 u64 clock, prev_clock_raw;
262 s64 clock_max_delta;
263
264 unsigned int clock_warps, clock_overflows;
265 unsigned int clock_unstable_events;
266
1da177e4
LT
267 atomic_t nr_iowait;
268
269#ifdef CONFIG_SMP
270 struct sched_domain *sd;
271
272 /* For active balancing */
273 int active_balance;
274 int push_cpu;
0a2966b4 275 int cpu; /* cpu of this runqueue */
1da177e4 276
36c8b586 277 struct task_struct *migration_thread;
1da177e4
LT
278 struct list_head migration_queue;
279#endif
280
281#ifdef CONFIG_SCHEDSTATS
282 /* latency stats */
283 struct sched_info rq_sched_info;
284
285 /* sys_sched_yield() stats */
286 unsigned long yld_exp_empty;
287 unsigned long yld_act_empty;
288 unsigned long yld_both_empty;
289 unsigned long yld_cnt;
290
291 /* schedule() stats */
292 unsigned long sched_switch;
293 unsigned long sched_cnt;
294 unsigned long sched_goidle;
295
296 /* try_to_wake_up() stats */
297 unsigned long ttwu_cnt;
298 unsigned long ttwu_local;
299#endif
fcb99371 300 struct lock_class_key rq_lock_key;
1da177e4
LT
301};
302
f34e3b61 303static DEFINE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);
5be9361c 304static DEFINE_MUTEX(sched_hotcpu_mutex);
1da177e4 305
dd41f596
IM
306static inline void check_preempt_curr(struct rq *rq, struct task_struct *p)
307{
308 rq->curr->sched_class->check_preempt_curr(rq, p);
309}
310
0a2966b4
CL
311static inline int cpu_of(struct rq *rq)
312{
313#ifdef CONFIG_SMP
314 return rq->cpu;
315#else
316 return 0;
317#endif
318}
319
20d315d4 320/*
b04a0f4c
IM
321 * Update the per-runqueue clock, as finegrained as the platform can give
322 * us, but without assuming monotonicity, etc.:
20d315d4 323 */
b04a0f4c 324static void __update_rq_clock(struct rq *rq)
20d315d4
IM
325{
326 u64 prev_raw = rq->prev_clock_raw;
327 u64 now = sched_clock();
328 s64 delta = now - prev_raw;
329 u64 clock = rq->clock;
330
b04a0f4c
IM
331#ifdef CONFIG_SCHED_DEBUG
332 WARN_ON_ONCE(cpu_of(rq) != smp_processor_id());
333#endif
20d315d4
IM
334 /*
335 * Protect against sched_clock() occasionally going backwards:
336 */
337 if (unlikely(delta < 0)) {
338 clock++;
339 rq->clock_warps++;
340 } else {
341 /*
342 * Catch too large forward jumps too:
343 */
344 if (unlikely(delta > 2*TICK_NSEC)) {
345 clock++;
346 rq->clock_overflows++;
347 } else {
348 if (unlikely(delta > rq->clock_max_delta))
349 rq->clock_max_delta = delta;
350 clock += delta;
351 }
352 }
353
354 rq->prev_clock_raw = now;
355 rq->clock = clock;
b04a0f4c 356}
20d315d4 357
b04a0f4c
IM
358static void update_rq_clock(struct rq *rq)
359{
360 if (likely(smp_processor_id() == cpu_of(rq)))
361 __update_rq_clock(rq);
20d315d4
IM
362}
363
674311d5
NP
364/*
365 * The domain tree (rq->sd) is protected by RCU's quiescent state transition.
1a20ff27 366 * See detach_destroy_domains: synchronize_sched for details.
674311d5
NP
367 *
368 * The domain tree of any CPU may only be accessed from within
369 * preempt-disabled sections.
370 */
48f24c4d
IM
371#define for_each_domain(cpu, __sd) \
372 for (__sd = rcu_dereference(cpu_rq(cpu)->sd); __sd; __sd = __sd->parent)
1da177e4
LT
373
374#define cpu_rq(cpu) (&per_cpu(runqueues, (cpu)))
375#define this_rq() (&__get_cpu_var(runqueues))
376#define task_rq(p) cpu_rq(task_cpu(p))
377#define cpu_curr(cpu) (cpu_rq(cpu)->curr)
378
e436d800
IM
379/*
380 * For kernel-internal use: high-speed (but slightly incorrect) per-cpu
381 * clock constructed from sched_clock():
382 */
383unsigned long long cpu_clock(int cpu)
384{
e436d800
IM
385 unsigned long long now;
386 unsigned long flags;
b04a0f4c 387 struct rq *rq;
e436d800 388
2cd4d0ea 389 local_irq_save(flags);
b04a0f4c
IM
390 rq = cpu_rq(cpu);
391 update_rq_clock(rq);
392 now = rq->clock;
2cd4d0ea 393 local_irq_restore(flags);
e436d800
IM
394
395 return now;
396}
397
138a8aeb
IM
398#ifdef CONFIG_FAIR_GROUP_SCHED
399/* Change a task's ->cfs_rq if it moves across CPUs */
400static inline void set_task_cfs_rq(struct task_struct *p)
401{
402 p->se.cfs_rq = &task_rq(p)->cfs;
403}
404#else
405static inline void set_task_cfs_rq(struct task_struct *p)
406{
407}
408#endif
409
1da177e4 410#ifndef prepare_arch_switch
4866cde0
NP
411# define prepare_arch_switch(next) do { } while (0)
412#endif
413#ifndef finish_arch_switch
414# define finish_arch_switch(prev) do { } while (0)
415#endif
416
417#ifndef __ARCH_WANT_UNLOCKED_CTXSW
70b97a7f 418static inline int task_running(struct rq *rq, struct task_struct *p)
4866cde0
NP
419{
420 return rq->curr == p;
421}
422
70b97a7f 423static inline void prepare_lock_switch(struct rq *rq, struct task_struct *next)
4866cde0
NP
424{
425}
426
70b97a7f 427static inline void finish_lock_switch(struct rq *rq, struct task_struct *prev)
4866cde0 428{
da04c035
IM
429#ifdef CONFIG_DEBUG_SPINLOCK
430 /* this is a valid case when another task releases the spinlock */
431 rq->lock.owner = current;
432#endif
8a25d5de
IM
433 /*
434 * If we are tracking spinlock dependencies then we have to
435 * fix up the runqueue lock - which gets 'carried over' from
436 * prev into current:
437 */
438 spin_acquire(&rq->lock.dep_map, 0, 0, _THIS_IP_);
439
4866cde0
NP
440 spin_unlock_irq(&rq->lock);
441}
442
443#else /* __ARCH_WANT_UNLOCKED_CTXSW */
70b97a7f 444static inline int task_running(struct rq *rq, struct task_struct *p)
4866cde0
NP
445{
446#ifdef CONFIG_SMP
447 return p->oncpu;
448#else
449 return rq->curr == p;
450#endif
451}
452
70b97a7f 453static inline void prepare_lock_switch(struct rq *rq, struct task_struct *next)
4866cde0
NP
454{
455#ifdef CONFIG_SMP
456 /*
457 * We can optimise this out completely for !SMP, because the
458 * SMP rebalancing from interrupt is the only thing that cares
459 * here.
460 */
461 next->oncpu = 1;
462#endif
463#ifdef __ARCH_WANT_INTERRUPTS_ON_CTXSW
464 spin_unlock_irq(&rq->lock);
465#else
466 spin_unlock(&rq->lock);
467#endif
468}
469
70b97a7f 470static inline void finish_lock_switch(struct rq *rq, struct task_struct *prev)
4866cde0
NP
471{
472#ifdef CONFIG_SMP
473 /*
474 * After ->oncpu is cleared, the task can be moved to a different CPU.
475 * We must ensure this doesn't happen until the switch is completely
476 * finished.
477 */
478 smp_wmb();
479 prev->oncpu = 0;
480#endif
481#ifndef __ARCH_WANT_INTERRUPTS_ON_CTXSW
482 local_irq_enable();
1da177e4 483#endif
4866cde0
NP
484}
485#endif /* __ARCH_WANT_UNLOCKED_CTXSW */
1da177e4 486
b29739f9
IM
487/*
488 * __task_rq_lock - lock the runqueue a given task resides on.
489 * Must be called interrupts disabled.
490 */
70b97a7f 491static inline struct rq *__task_rq_lock(struct task_struct *p)
b29739f9
IM
492 __acquires(rq->lock)
493{
70b97a7f 494 struct rq *rq;
b29739f9
IM
495
496repeat_lock_task:
497 rq = task_rq(p);
498 spin_lock(&rq->lock);
499 if (unlikely(rq != task_rq(p))) {
500 spin_unlock(&rq->lock);
501 goto repeat_lock_task;
502 }
503 return rq;
504}
505
1da177e4
LT
506/*
507 * task_rq_lock - lock the runqueue a given task resides on and disable
508 * interrupts. Note the ordering: we can safely lookup the task_rq without
509 * explicitly disabling preemption.
510 */
70b97a7f 511static struct rq *task_rq_lock(struct task_struct *p, unsigned long *flags)
1da177e4
LT
512 __acquires(rq->lock)
513{
70b97a7f 514 struct rq *rq;
1da177e4
LT
515
516repeat_lock_task:
517 local_irq_save(*flags);
518 rq = task_rq(p);
519 spin_lock(&rq->lock);
520 if (unlikely(rq != task_rq(p))) {
521 spin_unlock_irqrestore(&rq->lock, *flags);
522 goto repeat_lock_task;
523 }
524 return rq;
525}
526
70b97a7f 527static inline void __task_rq_unlock(struct rq *rq)
b29739f9
IM
528 __releases(rq->lock)
529{
530 spin_unlock(&rq->lock);
531}
532
70b97a7f 533static inline void task_rq_unlock(struct rq *rq, unsigned long *flags)
1da177e4
LT
534 __releases(rq->lock)
535{
536 spin_unlock_irqrestore(&rq->lock, *flags);
537}
538
1da177e4 539/*
cc2a73b5 540 * this_rq_lock - lock this runqueue and disable interrupts.
1da177e4 541 */
70b97a7f 542static inline struct rq *this_rq_lock(void)
1da177e4
LT
543 __acquires(rq->lock)
544{
70b97a7f 545 struct rq *rq;
1da177e4
LT
546
547 local_irq_disable();
548 rq = this_rq();
549 spin_lock(&rq->lock);
550
551 return rq;
552}
553
1b9f19c2
IM
554/*
555 * CPU frequency is/was unstable - start new by setting prev_clock_raw:
556 */
557void sched_clock_unstable_event(void)
558{
559 unsigned long flags;
560 struct rq *rq;
561
562 rq = task_rq_lock(current, &flags);
563 rq->prev_clock_raw = sched_clock();
564 rq->clock_unstable_events++;
565 task_rq_unlock(rq, &flags);
566}
567
c24d20db
IM
568/*
569 * resched_task - mark a task 'to be rescheduled now'.
570 *
571 * On UP this means the setting of the need_resched flag, on SMP it
572 * might also involve a cross-CPU call to trigger the scheduler on
573 * the target CPU.
574 */
575#ifdef CONFIG_SMP
576
577#ifndef tsk_is_polling
578#define tsk_is_polling(t) test_tsk_thread_flag(t, TIF_POLLING_NRFLAG)
579#endif
580
581static void resched_task(struct task_struct *p)
582{
583 int cpu;
584
585 assert_spin_locked(&task_rq(p)->lock);
586
587 if (unlikely(test_tsk_thread_flag(p, TIF_NEED_RESCHED)))
588 return;
589
590 set_tsk_thread_flag(p, TIF_NEED_RESCHED);
591
592 cpu = task_cpu(p);
593 if (cpu == smp_processor_id())
594 return;
595
596 /* NEED_RESCHED must be visible before we test polling */
597 smp_mb();
598 if (!tsk_is_polling(p))
599 smp_send_reschedule(cpu);
600}
601
602static void resched_cpu(int cpu)
603{
604 struct rq *rq = cpu_rq(cpu);
605 unsigned long flags;
606
607 if (!spin_trylock_irqsave(&rq->lock, flags))
608 return;
609 resched_task(cpu_curr(cpu));
610 spin_unlock_irqrestore(&rq->lock, flags);
611}
612#else
613static inline void resched_task(struct task_struct *p)
614{
615 assert_spin_locked(&task_rq(p)->lock);
616 set_tsk_need_resched(p);
617}
618#endif
619
45bf76df
IM
620static u64 div64_likely32(u64 divident, unsigned long divisor)
621{
622#if BITS_PER_LONG == 32
623 if (likely(divident <= 0xffffffffULL))
624 return (u32)divident / divisor;
625 do_div(divident, divisor);
626
627 return divident;
628#else
629 return divident / divisor;
630#endif
631}
632
633#if BITS_PER_LONG == 32
634# define WMULT_CONST (~0UL)
635#else
636# define WMULT_CONST (1UL << 32)
637#endif
638
639#define WMULT_SHIFT 32
640
cb1c4fc9 641static unsigned long
45bf76df
IM
642calc_delta_mine(unsigned long delta_exec, unsigned long weight,
643 struct load_weight *lw)
644{
645 u64 tmp;
646
647 if (unlikely(!lw->inv_weight))
648 lw->inv_weight = WMULT_CONST / lw->weight;
649
650 tmp = (u64)delta_exec * weight;
651 /*
652 * Check whether we'd overflow the 64-bit multiplication:
653 */
654 if (unlikely(tmp > WMULT_CONST)) {
655 tmp = ((tmp >> WMULT_SHIFT/2) * lw->inv_weight)
656 >> (WMULT_SHIFT/2);
657 } else {
658 tmp = (tmp * lw->inv_weight) >> WMULT_SHIFT;
659 }
660
ecf691da 661 return (unsigned long)min(tmp, (u64)(unsigned long)LONG_MAX);
45bf76df
IM
662}
663
664static inline unsigned long
665calc_delta_fair(unsigned long delta_exec, struct load_weight *lw)
666{
667 return calc_delta_mine(delta_exec, NICE_0_LOAD, lw);
668}
669
670static void update_load_add(struct load_weight *lw, unsigned long inc)
671{
672 lw->weight += inc;
673 lw->inv_weight = 0;
674}
675
676static void update_load_sub(struct load_weight *lw, unsigned long dec)
677{
678 lw->weight -= dec;
679 lw->inv_weight = 0;
680}
681
2dd73a4f
PW
682/*
683 * To aid in avoiding the subversion of "niceness" due to uneven distribution
684 * of tasks with abnormal "nice" values across CPUs the contribution that
685 * each task makes to its run queue's load is weighted according to its
686 * scheduling class and "nice" value. For SCHED_NORMAL tasks this is just a
687 * scaled version of the new time slice allocation that they receive on time
688 * slice expiry etc.
689 */
690
dd41f596
IM
691#define WEIGHT_IDLEPRIO 2
692#define WMULT_IDLEPRIO (1 << 31)
693
694/*
695 * Nice levels are multiplicative, with a gentle 10% change for every
696 * nice level changed. I.e. when a CPU-bound task goes from nice 0 to
697 * nice 1, it will get ~10% less CPU time than another CPU-bound task
698 * that remained on nice 0.
699 *
700 * The "10% effect" is relative and cumulative: from _any_ nice level,
701 * if you go up 1 level, it's -10% CPU usage, if you go down 1 level
f9153ee6
IM
702 * it's +10% CPU usage. (to achieve that we use a multiplier of 1.25.
703 * If a task goes up by ~10% and another task goes down by ~10% then
704 * the relative distance between them is ~25%.)
dd41f596
IM
705 */
706static const int prio_to_weight[40] = {
707/* -20 */ 88818, 71054, 56843, 45475, 36380, 29104, 23283, 18626, 14901, 11921,
708/* -10 */ 9537, 7629, 6103, 4883, 3906, 3125, 2500, 2000, 1600, 1280,
709/* 0 */ NICE_0_LOAD /* 1024 */,
710/* 1 */ 819, 655, 524, 419, 336, 268, 215, 172, 137,
711/* 10 */ 110, 87, 70, 56, 45, 36, 29, 23, 18, 15,
712};
713
5714d2de
IM
714/*
715 * Inverse (2^32/x) values of the prio_to_weight[] array, precalculated.
716 *
717 * In cases where the weight does not change often, we can use the
718 * precalculated inverse to speed up arithmetics by turning divisions
719 * into multiplications:
720 */
dd41f596 721static const u32 prio_to_wmult[40] = {
e4af30be
IM
722/* -20 */ 48356, 60446, 75558, 94446, 118058,
723/* -15 */ 147573, 184467, 230589, 288233, 360285,
724/* -10 */ 450347, 562979, 703746, 879575, 1099582,
725/* -5 */ 1374389, 1717986, 2147483, 2684354, 3355443,
726/* 0 */ 4194304, 5244160, 6557201, 8196502, 10250518,
727/* 5 */ 12782640, 16025997, 19976592, 24970740, 31350126,
728/* 10 */ 39045157, 49367440, 61356675, 76695844, 95443717,
729/* 15 */ 119304647, 148102320, 186737708, 238609294, 286331153,
dd41f596 730};
2dd73a4f 731
dd41f596
IM
732static void activate_task(struct rq *rq, struct task_struct *p, int wakeup);
733
734/*
735 * runqueue iterator, to support SMP load-balancing between different
736 * scheduling classes, without having to expose their internal data
737 * structures to the load-balancing proper:
738 */
739struct rq_iterator {
740 void *arg;
741 struct task_struct *(*start)(void *);
742 struct task_struct *(*next)(void *);
743};
744
745static int balance_tasks(struct rq *this_rq, int this_cpu, struct rq *busiest,
746 unsigned long max_nr_move, unsigned long max_load_move,
747 struct sched_domain *sd, enum cpu_idle_type idle,
748 int *all_pinned, unsigned long *load_moved,
a4ac01c3 749 int *this_best_prio, struct rq_iterator *iterator);
dd41f596
IM
750
751#include "sched_stats.h"
752#include "sched_rt.c"
753#include "sched_fair.c"
754#include "sched_idletask.c"
755#ifdef CONFIG_SCHED_DEBUG
756# include "sched_debug.c"
757#endif
758
759#define sched_class_highest (&rt_sched_class)
760
9c217245
IM
761static void __update_curr_load(struct rq *rq, struct load_stat *ls)
762{
763 if (rq->curr != rq->idle && ls->load.weight) {
764 ls->delta_exec += ls->delta_stat;
765 ls->delta_fair += calc_delta_fair(ls->delta_stat, &ls->load);
766 ls->delta_stat = 0;
767 }
768}
769
770/*
771 * Update delta_exec, delta_fair fields for rq.
772 *
773 * delta_fair clock advances at a rate inversely proportional to
774 * total load (rq->ls.load.weight) on the runqueue, while
775 * delta_exec advances at the same rate as wall-clock (provided
776 * cpu is not idle).
777 *
778 * delta_exec / delta_fair is a measure of the (smoothened) load on this
779 * runqueue over any given interval. This (smoothened) load is used
780 * during load balance.
781 *
782 * This function is called /before/ updating rq->ls.load
783 * and when switching tasks.
784 */
84a1d7a2 785static void update_curr_load(struct rq *rq)
9c217245
IM
786{
787 struct load_stat *ls = &rq->ls;
788 u64 start;
789
790 start = ls->load_update_start;
d281918d
IM
791 ls->load_update_start = rq->clock;
792 ls->delta_stat += rq->clock - start;
9c217245
IM
793 /*
794 * Stagger updates to ls->delta_fair. Very frequent updates
795 * can be expensive.
796 */
797 if (ls->delta_stat >= sysctl_sched_stat_granularity)
798 __update_curr_load(rq, ls);
799}
800
29b4b623 801static inline void inc_load(struct rq *rq, const struct task_struct *p)
9c217245 802{
84a1d7a2 803 update_curr_load(rq);
9c217245
IM
804 update_load_add(&rq->ls.load, p->se.load.weight);
805}
806
79b5dddf 807static inline void dec_load(struct rq *rq, const struct task_struct *p)
9c217245 808{
84a1d7a2 809 update_curr_load(rq);
9c217245
IM
810 update_load_sub(&rq->ls.load, p->se.load.weight);
811}
812
e5fa2237 813static void inc_nr_running(struct task_struct *p, struct rq *rq)
9c217245
IM
814{
815 rq->nr_running++;
29b4b623 816 inc_load(rq, p);
9c217245
IM
817}
818
db53181e 819static void dec_nr_running(struct task_struct *p, struct rq *rq)
9c217245
IM
820{
821 rq->nr_running--;
79b5dddf 822 dec_load(rq, p);
9c217245
IM
823}
824
45bf76df
IM
825static void set_load_weight(struct task_struct *p)
826{
dd41f596
IM
827 task_rq(p)->cfs.wait_runtime -= p->se.wait_runtime;
828 p->se.wait_runtime = 0;
829
45bf76df 830 if (task_has_rt_policy(p)) {
dd41f596
IM
831 p->se.load.weight = prio_to_weight[0] * 2;
832 p->se.load.inv_weight = prio_to_wmult[0] >> 1;
833 return;
834 }
45bf76df 835
dd41f596
IM
836 /*
837 * SCHED_IDLE tasks get minimal weight:
838 */
839 if (p->policy == SCHED_IDLE) {
840 p->se.load.weight = WEIGHT_IDLEPRIO;
841 p->se.load.inv_weight = WMULT_IDLEPRIO;
842 return;
843 }
71f8bd46 844
dd41f596
IM
845 p->se.load.weight = prio_to_weight[p->static_prio - MAX_RT_PRIO];
846 p->se.load.inv_weight = prio_to_wmult[p->static_prio - MAX_RT_PRIO];
71f8bd46
IM
847}
848
8159f87e 849static void enqueue_task(struct rq *rq, struct task_struct *p, int wakeup)
71f8bd46 850{
dd41f596 851 sched_info_queued(p);
fd390f6a 852 p->sched_class->enqueue_task(rq, p, wakeup);
dd41f596 853 p->se.on_rq = 1;
71f8bd46
IM
854}
855
69be72c1 856static void dequeue_task(struct rq *rq, struct task_struct *p, int sleep)
71f8bd46 857{
f02231e5 858 p->sched_class->dequeue_task(rq, p, sleep);
dd41f596 859 p->se.on_rq = 0;
71f8bd46
IM
860}
861
14531189 862/*
dd41f596 863 * __normal_prio - return the priority that is based on the static prio
14531189 864 */
14531189
IM
865static inline int __normal_prio(struct task_struct *p)
866{
dd41f596 867 return p->static_prio;
14531189
IM
868}
869
b29739f9
IM
870/*
871 * Calculate the expected normal priority: i.e. priority
872 * without taking RT-inheritance into account. Might be
873 * boosted by interactivity modifiers. Changes upon fork,
874 * setprio syscalls, and whenever the interactivity
875 * estimator recalculates.
876 */
36c8b586 877static inline int normal_prio(struct task_struct *p)
b29739f9
IM
878{
879 int prio;
880
e05606d3 881 if (task_has_rt_policy(p))
b29739f9
IM
882 prio = MAX_RT_PRIO-1 - p->rt_priority;
883 else
884 prio = __normal_prio(p);
885 return prio;
886}
887
888/*
889 * Calculate the current priority, i.e. the priority
890 * taken into account by the scheduler. This value might
891 * be boosted by RT tasks, or might be boosted by
892 * interactivity modifiers. Will be RT if the task got
893 * RT-boosted. If not then it returns p->normal_prio.
894 */
36c8b586 895static int effective_prio(struct task_struct *p)
b29739f9
IM
896{
897 p->normal_prio = normal_prio(p);
898 /*
899 * If we are RT tasks or we were boosted to RT priority,
900 * keep the priority unchanged. Otherwise, update priority
901 * to the normal priority:
902 */
903 if (!rt_prio(p->prio))
904 return p->normal_prio;
905 return p->prio;
906}
907
1da177e4 908/*
dd41f596 909 * activate_task - move a task to the runqueue.
1da177e4 910 */
dd41f596 911static void activate_task(struct rq *rq, struct task_struct *p, int wakeup)
1da177e4 912{
a8e504d2 913 update_rq_clock(rq);
d425b274 914
dd41f596
IM
915 if (p->state == TASK_UNINTERRUPTIBLE)
916 rq->nr_uninterruptible--;
1da177e4 917
8159f87e 918 enqueue_task(rq, p, wakeup);
e5fa2237 919 inc_nr_running(p, rq);
1da177e4
LT
920}
921
922/*
dd41f596 923 * activate_idle_task - move idle task to the _front_ of runqueue.
1da177e4 924 */
dd41f596 925static inline void activate_idle_task(struct task_struct *p, struct rq *rq)
1da177e4 926{
a8e504d2 927 update_rq_clock(rq);
1da177e4 928
dd41f596
IM
929 if (p->state == TASK_UNINTERRUPTIBLE)
930 rq->nr_uninterruptible--;
ece8a684 931
8159f87e 932 enqueue_task(rq, p, 0);
e5fa2237 933 inc_nr_running(p, rq);
1da177e4
LT
934}
935
936/*
937 * deactivate_task - remove a task from the runqueue.
938 */
2e1cb74a 939static void deactivate_task(struct rq *rq, struct task_struct *p, int sleep)
1da177e4 940{
dd41f596
IM
941 if (p->state == TASK_UNINTERRUPTIBLE)
942 rq->nr_uninterruptible++;
943
69be72c1 944 dequeue_task(rq, p, sleep);
db53181e 945 dec_nr_running(p, rq);
1da177e4
LT
946}
947
1da177e4
LT
948/**
949 * task_curr - is this task currently executing on a CPU?
950 * @p: the task in question.
951 */
36c8b586 952inline int task_curr(const struct task_struct *p)
1da177e4
LT
953{
954 return cpu_curr(task_cpu(p)) == p;
955}
956
2dd73a4f
PW
957/* Used instead of source_load when we know the type == 0 */
958unsigned long weighted_cpuload(const int cpu)
959{
dd41f596
IM
960 return cpu_rq(cpu)->ls.load.weight;
961}
962
963static inline void __set_task_cpu(struct task_struct *p, unsigned int cpu)
964{
965#ifdef CONFIG_SMP
966 task_thread_info(p)->cpu = cpu;
967 set_task_cfs_rq(p);
968#endif
2dd73a4f
PW
969}
970
1da177e4 971#ifdef CONFIG_SMP
c65cc870 972
dd41f596 973void set_task_cpu(struct task_struct *p, unsigned int new_cpu)
c65cc870 974{
dd41f596
IM
975 int old_cpu = task_cpu(p);
976 struct rq *old_rq = cpu_rq(old_cpu), *new_rq = cpu_rq(new_cpu);
977 u64 clock_offset, fair_clock_offset;
978
979 clock_offset = old_rq->clock - new_rq->clock;
6cfb0d5d
IM
980 fair_clock_offset = old_rq->cfs.fair_clock - new_rq->cfs.fair_clock;
981
dd41f596
IM
982 if (p->se.wait_start_fair)
983 p->se.wait_start_fair -= fair_clock_offset;
6cfb0d5d
IM
984 if (p->se.sleep_start_fair)
985 p->se.sleep_start_fair -= fair_clock_offset;
986
987#ifdef CONFIG_SCHEDSTATS
988 if (p->se.wait_start)
989 p->se.wait_start -= clock_offset;
dd41f596
IM
990 if (p->se.sleep_start)
991 p->se.sleep_start -= clock_offset;
992 if (p->se.block_start)
993 p->se.block_start -= clock_offset;
6cfb0d5d 994#endif
dd41f596
IM
995
996 __set_task_cpu(p, new_cpu);
c65cc870
IM
997}
998
70b97a7f 999struct migration_req {
1da177e4 1000 struct list_head list;
1da177e4 1001
36c8b586 1002 struct task_struct *task;
1da177e4
LT
1003 int dest_cpu;
1004
1da177e4 1005 struct completion done;
70b97a7f 1006};
1da177e4
LT
1007
1008/*
1009 * The task's runqueue lock must be held.
1010 * Returns true if you have to wait for migration thread.
1011 */
36c8b586 1012static int
70b97a7f 1013migrate_task(struct task_struct *p, int dest_cpu, struct migration_req *req)
1da177e4 1014{
70b97a7f 1015 struct rq *rq = task_rq(p);
1da177e4
LT
1016
1017 /*
1018 * If the task is not on a runqueue (and not running), then
1019 * it is sufficient to simply update the task's cpu field.
1020 */
dd41f596 1021 if (!p->se.on_rq && !task_running(rq, p)) {
1da177e4
LT
1022 set_task_cpu(p, dest_cpu);
1023 return 0;
1024 }
1025
1026 init_completion(&req->done);
1da177e4
LT
1027 req->task = p;
1028 req->dest_cpu = dest_cpu;
1029 list_add(&req->list, &rq->migration_queue);
48f24c4d 1030
1da177e4
LT
1031 return 1;
1032}
1033
1034/*
1035 * wait_task_inactive - wait for a thread to unschedule.
1036 *
1037 * The caller must ensure that the task *will* unschedule sometime soon,
1038 * else this function might spin for a *long* time. This function can't
1039 * be called with interrupts off, or it may introduce deadlock with
1040 * smp_call_function() if an IPI is sent by the same process we are
1041 * waiting to become inactive.
1042 */
36c8b586 1043void wait_task_inactive(struct task_struct *p)
1da177e4
LT
1044{
1045 unsigned long flags;
dd41f596 1046 int running, on_rq;
70b97a7f 1047 struct rq *rq;
1da177e4
LT
1048
1049repeat:
fa490cfd
LT
1050 /*
1051 * We do the initial early heuristics without holding
1052 * any task-queue locks at all. We'll only try to get
1053 * the runqueue lock when things look like they will
1054 * work out!
1055 */
1056 rq = task_rq(p);
1057
1058 /*
1059 * If the task is actively running on another CPU
1060 * still, just relax and busy-wait without holding
1061 * any locks.
1062 *
1063 * NOTE! Since we don't hold any locks, it's not
1064 * even sure that "rq" stays as the right runqueue!
1065 * But we don't care, since "task_running()" will
1066 * return false if the runqueue has changed and p
1067 * is actually now running somewhere else!
1068 */
1069 while (task_running(rq, p))
1070 cpu_relax();
1071
1072 /*
1073 * Ok, time to look more closely! We need the rq
1074 * lock now, to be *sure*. If we're wrong, we'll
1075 * just go back and repeat.
1076 */
1da177e4 1077 rq = task_rq_lock(p, &flags);
fa490cfd 1078 running = task_running(rq, p);
dd41f596 1079 on_rq = p->se.on_rq;
fa490cfd
LT
1080 task_rq_unlock(rq, &flags);
1081
1082 /*
1083 * Was it really running after all now that we
1084 * checked with the proper locks actually held?
1085 *
1086 * Oops. Go back and try again..
1087 */
1088 if (unlikely(running)) {
1da177e4 1089 cpu_relax();
1da177e4
LT
1090 goto repeat;
1091 }
fa490cfd
LT
1092
1093 /*
1094 * It's not enough that it's not actively running,
1095 * it must be off the runqueue _entirely_, and not
1096 * preempted!
1097 *
1098 * So if it wa still runnable (but just not actively
1099 * running right now), it's preempted, and we should
1100 * yield - it could be a while.
1101 */
dd41f596 1102 if (unlikely(on_rq)) {
fa490cfd
LT
1103 yield();
1104 goto repeat;
1105 }
1106
1107 /*
1108 * Ahh, all good. It wasn't running, and it wasn't
1109 * runnable, which means that it will never become
1110 * running in the future either. We're all done!
1111 */
1da177e4
LT
1112}
1113
1114/***
1115 * kick_process - kick a running thread to enter/exit the kernel
1116 * @p: the to-be-kicked thread
1117 *
1118 * Cause a process which is running on another CPU to enter
1119 * kernel-mode, without any delay. (to get signals handled.)
1120 *
1121 * NOTE: this function doesnt have to take the runqueue lock,
1122 * because all it wants to ensure is that the remote task enters
1123 * the kernel. If the IPI races and the task has been migrated
1124 * to another CPU then no harm is done and the purpose has been
1125 * achieved as well.
1126 */
36c8b586 1127void kick_process(struct task_struct *p)
1da177e4
LT
1128{
1129 int cpu;
1130
1131 preempt_disable();
1132 cpu = task_cpu(p);
1133 if ((cpu != smp_processor_id()) && task_curr(p))
1134 smp_send_reschedule(cpu);
1135 preempt_enable();
1136}
1137
1138/*
2dd73a4f
PW
1139 * Return a low guess at the load of a migration-source cpu weighted
1140 * according to the scheduling class and "nice" value.
1da177e4
LT
1141 *
1142 * We want to under-estimate the load of migration sources, to
1143 * balance conservatively.
1144 */
a2000572 1145static inline unsigned long source_load(int cpu, int type)
1da177e4 1146{
70b97a7f 1147 struct rq *rq = cpu_rq(cpu);
dd41f596 1148 unsigned long total = weighted_cpuload(cpu);
2dd73a4f 1149
3b0bd9bc 1150 if (type == 0)
dd41f596 1151 return total;
b910472d 1152
dd41f596 1153 return min(rq->cpu_load[type-1], total);
1da177e4
LT
1154}
1155
1156/*
2dd73a4f
PW
1157 * Return a high guess at the load of a migration-target cpu weighted
1158 * according to the scheduling class and "nice" value.
1da177e4 1159 */
a2000572 1160static inline unsigned long target_load(int cpu, int type)
1da177e4 1161{
70b97a7f 1162 struct rq *rq = cpu_rq(cpu);
dd41f596 1163 unsigned long total = weighted_cpuload(cpu);
2dd73a4f 1164
7897986b 1165 if (type == 0)
dd41f596 1166 return total;
3b0bd9bc 1167
dd41f596 1168 return max(rq->cpu_load[type-1], total);
2dd73a4f
PW
1169}
1170
1171/*
1172 * Return the average load per task on the cpu's run queue
1173 */
1174static inline unsigned long cpu_avg_load_per_task(int cpu)
1175{
70b97a7f 1176 struct rq *rq = cpu_rq(cpu);
dd41f596 1177 unsigned long total = weighted_cpuload(cpu);
2dd73a4f
PW
1178 unsigned long n = rq->nr_running;
1179
dd41f596 1180 return n ? total / n : SCHED_LOAD_SCALE;
1da177e4
LT
1181}
1182
147cbb4b
NP
1183/*
1184 * find_idlest_group finds and returns the least busy CPU group within the
1185 * domain.
1186 */
1187static struct sched_group *
1188find_idlest_group(struct sched_domain *sd, struct task_struct *p, int this_cpu)
1189{
1190 struct sched_group *idlest = NULL, *this = NULL, *group = sd->groups;
1191 unsigned long min_load = ULONG_MAX, this_load = 0;
1192 int load_idx = sd->forkexec_idx;
1193 int imbalance = 100 + (sd->imbalance_pct-100)/2;
1194
1195 do {
1196 unsigned long load, avg_load;
1197 int local_group;
1198 int i;
1199
da5a5522
BD
1200 /* Skip over this group if it has no CPUs allowed */
1201 if (!cpus_intersects(group->cpumask, p->cpus_allowed))
1202 goto nextgroup;
1203
147cbb4b 1204 local_group = cpu_isset(this_cpu, group->cpumask);
147cbb4b
NP
1205
1206 /* Tally up the load of all CPUs in the group */
1207 avg_load = 0;
1208
1209 for_each_cpu_mask(i, group->cpumask) {
1210 /* Bias balancing toward cpus of our domain */
1211 if (local_group)
1212 load = source_load(i, load_idx);
1213 else
1214 load = target_load(i, load_idx);
1215
1216 avg_load += load;
1217 }
1218
1219 /* Adjust by relative CPU power of the group */
5517d86b
ED
1220 avg_load = sg_div_cpu_power(group,
1221 avg_load * SCHED_LOAD_SCALE);
147cbb4b
NP
1222
1223 if (local_group) {
1224 this_load = avg_load;
1225 this = group;
1226 } else if (avg_load < min_load) {
1227 min_load = avg_load;
1228 idlest = group;
1229 }
da5a5522 1230nextgroup:
147cbb4b
NP
1231 group = group->next;
1232 } while (group != sd->groups);
1233
1234 if (!idlest || 100*this_load < imbalance*min_load)
1235 return NULL;
1236 return idlest;
1237}
1238
1239/*
0feaece9 1240 * find_idlest_cpu - find the idlest cpu among the cpus in group.
147cbb4b 1241 */
95cdf3b7
IM
1242static int
1243find_idlest_cpu(struct sched_group *group, struct task_struct *p, int this_cpu)
147cbb4b 1244{
da5a5522 1245 cpumask_t tmp;
147cbb4b
NP
1246 unsigned long load, min_load = ULONG_MAX;
1247 int idlest = -1;
1248 int i;
1249
da5a5522
BD
1250 /* Traverse only the allowed CPUs */
1251 cpus_and(tmp, group->cpumask, p->cpus_allowed);
1252
1253 for_each_cpu_mask(i, tmp) {
2dd73a4f 1254 load = weighted_cpuload(i);
147cbb4b
NP
1255
1256 if (load < min_load || (load == min_load && i == this_cpu)) {
1257 min_load = load;
1258 idlest = i;
1259 }
1260 }
1261
1262 return idlest;
1263}
1264
476d139c
NP
1265/*
1266 * sched_balance_self: balance the current task (running on cpu) in domains
1267 * that have the 'flag' flag set. In practice, this is SD_BALANCE_FORK and
1268 * SD_BALANCE_EXEC.
1269 *
1270 * Balance, ie. select the least loaded group.
1271 *
1272 * Returns the target CPU number, or the same CPU if no balancing is needed.
1273 *
1274 * preempt must be disabled.
1275 */
1276static int sched_balance_self(int cpu, int flag)
1277{
1278 struct task_struct *t = current;
1279 struct sched_domain *tmp, *sd = NULL;
147cbb4b 1280
c96d145e 1281 for_each_domain(cpu, tmp) {
9761eea8
IM
1282 /*
1283 * If power savings logic is enabled for a domain, stop there.
1284 */
5c45bf27
SS
1285 if (tmp->flags & SD_POWERSAVINGS_BALANCE)
1286 break;
476d139c
NP
1287 if (tmp->flags & flag)
1288 sd = tmp;
c96d145e 1289 }
476d139c
NP
1290
1291 while (sd) {
1292 cpumask_t span;
1293 struct sched_group *group;
1a848870
SS
1294 int new_cpu, weight;
1295
1296 if (!(sd->flags & flag)) {
1297 sd = sd->child;
1298 continue;
1299 }
476d139c
NP
1300
1301 span = sd->span;
1302 group = find_idlest_group(sd, t, cpu);
1a848870
SS
1303 if (!group) {
1304 sd = sd->child;
1305 continue;
1306 }
476d139c 1307
da5a5522 1308 new_cpu = find_idlest_cpu(group, t, cpu);
1a848870
SS
1309 if (new_cpu == -1 || new_cpu == cpu) {
1310 /* Now try balancing at a lower domain level of cpu */
1311 sd = sd->child;
1312 continue;
1313 }
476d139c 1314
1a848870 1315 /* Now try balancing at a lower domain level of new_cpu */
476d139c 1316 cpu = new_cpu;
476d139c
NP
1317 sd = NULL;
1318 weight = cpus_weight(span);
1319 for_each_domain(cpu, tmp) {
1320 if (weight <= cpus_weight(tmp->span))
1321 break;
1322 if (tmp->flags & flag)
1323 sd = tmp;
1324 }
1325 /* while loop will break here if sd == NULL */
1326 }
1327
1328 return cpu;
1329}
1330
1331#endif /* CONFIG_SMP */
1da177e4
LT
1332
1333/*
1334 * wake_idle() will wake a task on an idle cpu if task->cpu is
1335 * not idle and an idle cpu is available. The span of cpus to
1336 * search starts with cpus closest then further out as needed,
1337 * so we always favor a closer, idle cpu.
1338 *
1339 * Returns the CPU we should wake onto.
1340 */
1341#if defined(ARCH_HAS_SCHED_WAKE_IDLE)
36c8b586 1342static int wake_idle(int cpu, struct task_struct *p)
1da177e4
LT
1343{
1344 cpumask_t tmp;
1345 struct sched_domain *sd;
1346 int i;
1347
4953198b
SS
1348 /*
1349 * If it is idle, then it is the best cpu to run this task.
1350 *
1351 * This cpu is also the best, if it has more than one task already.
1352 * Siblings must be also busy(in most cases) as they didn't already
1353 * pickup the extra load from this cpu and hence we need not check
1354 * sibling runqueue info. This will avoid the checks and cache miss
1355 * penalities associated with that.
1356 */
1357 if (idle_cpu(cpu) || cpu_rq(cpu)->nr_running > 1)
1da177e4
LT
1358 return cpu;
1359
1360 for_each_domain(cpu, sd) {
1361 if (sd->flags & SD_WAKE_IDLE) {
e0f364f4 1362 cpus_and(tmp, sd->span, p->cpus_allowed);
1da177e4
LT
1363 for_each_cpu_mask(i, tmp) {
1364 if (idle_cpu(i))
1365 return i;
1366 }
9761eea8 1367 } else {
e0f364f4 1368 break;
9761eea8 1369 }
1da177e4
LT
1370 }
1371 return cpu;
1372}
1373#else
36c8b586 1374static inline int wake_idle(int cpu, struct task_struct *p)
1da177e4
LT
1375{
1376 return cpu;
1377}
1378#endif
1379
1380/***
1381 * try_to_wake_up - wake up a thread
1382 * @p: the to-be-woken-up thread
1383 * @state: the mask of task states that can be woken
1384 * @sync: do a synchronous wakeup?
1385 *
1386 * Put it on the run-queue if it's not already there. The "current"
1387 * thread is always on the run-queue (except when the actual
1388 * re-schedule is in progress), and as such you're allowed to do
1389 * the simpler "current->state = TASK_RUNNING" to mark yourself
1390 * runnable without the overhead of this.
1391 *
1392 * returns failure only if the task is already active.
1393 */
36c8b586 1394static int try_to_wake_up(struct task_struct *p, unsigned int state, int sync)
1da177e4
LT
1395{
1396 int cpu, this_cpu, success = 0;
1397 unsigned long flags;
1398 long old_state;
70b97a7f 1399 struct rq *rq;
1da177e4 1400#ifdef CONFIG_SMP
7897986b 1401 struct sched_domain *sd, *this_sd = NULL;
70b97a7f 1402 unsigned long load, this_load;
1da177e4
LT
1403 int new_cpu;
1404#endif
1405
1406 rq = task_rq_lock(p, &flags);
1407 old_state = p->state;
1408 if (!(old_state & state))
1409 goto out;
1410
dd41f596 1411 if (p->se.on_rq)
1da177e4
LT
1412 goto out_running;
1413
1414 cpu = task_cpu(p);
1415 this_cpu = smp_processor_id();
1416
1417#ifdef CONFIG_SMP
1418 if (unlikely(task_running(rq, p)))
1419 goto out_activate;
1420
7897986b
NP
1421 new_cpu = cpu;
1422
1da177e4
LT
1423 schedstat_inc(rq, ttwu_cnt);
1424 if (cpu == this_cpu) {
1425 schedstat_inc(rq, ttwu_local);
7897986b
NP
1426 goto out_set_cpu;
1427 }
1428
1429 for_each_domain(this_cpu, sd) {
1430 if (cpu_isset(cpu, sd->span)) {
1431 schedstat_inc(sd, ttwu_wake_remote);
1432 this_sd = sd;
1433 break;
1da177e4
LT
1434 }
1435 }
1da177e4 1436
7897986b 1437 if (unlikely(!cpu_isset(this_cpu, p->cpus_allowed)))
1da177e4
LT
1438 goto out_set_cpu;
1439
1da177e4 1440 /*
7897986b 1441 * Check for affine wakeup and passive balancing possibilities.
1da177e4 1442 */
7897986b
NP
1443 if (this_sd) {
1444 int idx = this_sd->wake_idx;
1445 unsigned int imbalance;
1da177e4 1446
a3f21bce
NP
1447 imbalance = 100 + (this_sd->imbalance_pct - 100) / 2;
1448
7897986b
NP
1449 load = source_load(cpu, idx);
1450 this_load = target_load(this_cpu, idx);
1da177e4 1451
7897986b
NP
1452 new_cpu = this_cpu; /* Wake to this CPU if we can */
1453
a3f21bce
NP
1454 if (this_sd->flags & SD_WAKE_AFFINE) {
1455 unsigned long tl = this_load;
33859f7f
MOS
1456 unsigned long tl_per_task;
1457
1458 tl_per_task = cpu_avg_load_per_task(this_cpu);
2dd73a4f 1459
1da177e4 1460 /*
a3f21bce
NP
1461 * If sync wakeup then subtract the (maximum possible)
1462 * effect of the currently running task from the load
1463 * of the current CPU:
1da177e4 1464 */
a3f21bce 1465 if (sync)
dd41f596 1466 tl -= current->se.load.weight;
a3f21bce
NP
1467
1468 if ((tl <= load &&
2dd73a4f 1469 tl + target_load(cpu, idx) <= tl_per_task) ||
dd41f596 1470 100*(tl + p->se.load.weight) <= imbalance*load) {
a3f21bce
NP
1471 /*
1472 * This domain has SD_WAKE_AFFINE and
1473 * p is cache cold in this domain, and
1474 * there is no bad imbalance.
1475 */
1476 schedstat_inc(this_sd, ttwu_move_affine);
1477 goto out_set_cpu;
1478 }
1479 }
1480
1481 /*
1482 * Start passive balancing when half the imbalance_pct
1483 * limit is reached.
1484 */
1485 if (this_sd->flags & SD_WAKE_BALANCE) {
1486 if (imbalance*this_load <= 100*load) {
1487 schedstat_inc(this_sd, ttwu_move_balance);
1488 goto out_set_cpu;
1489 }
1da177e4
LT
1490 }
1491 }
1492
1493 new_cpu = cpu; /* Could not wake to this_cpu. Wake to cpu instead */
1494out_set_cpu:
1495 new_cpu = wake_idle(new_cpu, p);
1496 if (new_cpu != cpu) {
1497 set_task_cpu(p, new_cpu);
1498 task_rq_unlock(rq, &flags);
1499 /* might preempt at this point */
1500 rq = task_rq_lock(p, &flags);
1501 old_state = p->state;
1502 if (!(old_state & state))
1503 goto out;
dd41f596 1504 if (p->se.on_rq)
1da177e4
LT
1505 goto out_running;
1506
1507 this_cpu = smp_processor_id();
1508 cpu = task_cpu(p);
1509 }
1510
1511out_activate:
1512#endif /* CONFIG_SMP */
dd41f596 1513 activate_task(rq, p, 1);
1da177e4
LT
1514 /*
1515 * Sync wakeups (i.e. those types of wakeups where the waker
1516 * has indicated that it will leave the CPU in short order)
1517 * don't trigger a preemption, if the woken up task will run on
1518 * this cpu. (in this case the 'I will reschedule' promise of
1519 * the waker guarantees that the freshly woken up task is going
1520 * to be considered on this CPU.)
1521 */
dd41f596
IM
1522 if (!sync || cpu != this_cpu)
1523 check_preempt_curr(rq, p);
1da177e4
LT
1524 success = 1;
1525
1526out_running:
1527 p->state = TASK_RUNNING;
1528out:
1529 task_rq_unlock(rq, &flags);
1530
1531 return success;
1532}
1533
36c8b586 1534int fastcall wake_up_process(struct task_struct *p)
1da177e4
LT
1535{
1536 return try_to_wake_up(p, TASK_STOPPED | TASK_TRACED |
1537 TASK_INTERRUPTIBLE | TASK_UNINTERRUPTIBLE, 0);
1538}
1da177e4
LT
1539EXPORT_SYMBOL(wake_up_process);
1540
36c8b586 1541int fastcall wake_up_state(struct task_struct *p, unsigned int state)
1da177e4
LT
1542{
1543 return try_to_wake_up(p, state, 0);
1544}
1545
1da177e4
LT
1546/*
1547 * Perform scheduler related setup for a newly forked process p.
1548 * p is forked by current.
dd41f596
IM
1549 *
1550 * __sched_fork() is basic setup used by init_idle() too:
1551 */
1552static void __sched_fork(struct task_struct *p)
1553{
1554 p->se.wait_start_fair = 0;
dd41f596
IM
1555 p->se.exec_start = 0;
1556 p->se.sum_exec_runtime = 0;
1557 p->se.delta_exec = 0;
1558 p->se.delta_fair_run = 0;
1559 p->se.delta_fair_sleep = 0;
1560 p->se.wait_runtime = 0;
6cfb0d5d
IM
1561 p->se.sleep_start_fair = 0;
1562
1563#ifdef CONFIG_SCHEDSTATS
1564 p->se.wait_start = 0;
dd41f596
IM
1565 p->se.sum_wait_runtime = 0;
1566 p->se.sum_sleep_runtime = 0;
1567 p->se.sleep_start = 0;
dd41f596
IM
1568 p->se.block_start = 0;
1569 p->se.sleep_max = 0;
1570 p->se.block_max = 0;
1571 p->se.exec_max = 0;
1572 p->se.wait_max = 0;
1573 p->se.wait_runtime_overruns = 0;
1574 p->se.wait_runtime_underruns = 0;
6cfb0d5d 1575#endif
476d139c 1576
dd41f596
IM
1577 INIT_LIST_HEAD(&p->run_list);
1578 p->se.on_rq = 0;
476d139c 1579
e107be36
AK
1580#ifdef CONFIG_PREEMPT_NOTIFIERS
1581 INIT_HLIST_HEAD(&p->preempt_notifiers);
1582#endif
1583
1da177e4
LT
1584 /*
1585 * We mark the process as running here, but have not actually
1586 * inserted it onto the runqueue yet. This guarantees that
1587 * nobody will actually run it, and a signal or other external
1588 * event cannot wake it up and insert it on the runqueue either.
1589 */
1590 p->state = TASK_RUNNING;
dd41f596
IM
1591}
1592
1593/*
1594 * fork()/clone()-time setup:
1595 */
1596void sched_fork(struct task_struct *p, int clone_flags)
1597{
1598 int cpu = get_cpu();
1599
1600 __sched_fork(p);
1601
1602#ifdef CONFIG_SMP
1603 cpu = sched_balance_self(cpu, SD_BALANCE_FORK);
1604#endif
1605 __set_task_cpu(p, cpu);
b29739f9
IM
1606
1607 /*
1608 * Make sure we do not leak PI boosting priority to the child:
1609 */
1610 p->prio = current->normal_prio;
1611
52f17b6c 1612#if defined(CONFIG_SCHEDSTATS) || defined(CONFIG_TASK_DELAY_ACCT)
dd41f596 1613 if (likely(sched_info_on()))
52f17b6c 1614 memset(&p->sched_info, 0, sizeof(p->sched_info));
1da177e4 1615#endif
d6077cb8 1616#if defined(CONFIG_SMP) && defined(__ARCH_WANT_UNLOCKED_CTXSW)
4866cde0
NP
1617 p->oncpu = 0;
1618#endif
1da177e4 1619#ifdef CONFIG_PREEMPT
4866cde0 1620 /* Want to start with kernel preemption disabled. */
a1261f54 1621 task_thread_info(p)->preempt_count = 1;
1da177e4 1622#endif
476d139c 1623 put_cpu();
1da177e4
LT
1624}
1625
dd41f596
IM
1626/*
1627 * After fork, child runs first. (default) If set to 0 then
1628 * parent will (try to) run first.
1629 */
1630unsigned int __read_mostly sysctl_sched_child_runs_first = 1;
1631
1da177e4
LT
1632/*
1633 * wake_up_new_task - wake up a newly created task for the first time.
1634 *
1635 * This function will do some initial scheduler statistics housekeeping
1636 * that must be done for every newly created context, then puts the task
1637 * on the runqueue and wakes it.
1638 */
36c8b586 1639void fastcall wake_up_new_task(struct task_struct *p, unsigned long clone_flags)
1da177e4
LT
1640{
1641 unsigned long flags;
dd41f596
IM
1642 struct rq *rq;
1643 int this_cpu;
1da177e4
LT
1644
1645 rq = task_rq_lock(p, &flags);
147cbb4b 1646 BUG_ON(p->state != TASK_RUNNING);
dd41f596 1647 this_cpu = smp_processor_id(); /* parent's CPU */
a8e504d2 1648 update_rq_clock(rq);
1da177e4
LT
1649
1650 p->prio = effective_prio(p);
1651
cad60d93
IM
1652 if (!p->sched_class->task_new || !sysctl_sched_child_runs_first ||
1653 (clone_flags & CLONE_VM) || task_cpu(p) != this_cpu ||
1654 !current->se.on_rq) {
1655
dd41f596 1656 activate_task(rq, p, 0);
1da177e4 1657 } else {
1da177e4 1658 /*
dd41f596
IM
1659 * Let the scheduling class do new task startup
1660 * management (if any):
1da177e4 1661 */
ee0827d8 1662 p->sched_class->task_new(rq, p);
e5fa2237 1663 inc_nr_running(p, rq);
1da177e4 1664 }
dd41f596
IM
1665 check_preempt_curr(rq, p);
1666 task_rq_unlock(rq, &flags);
1da177e4
LT
1667}
1668
e107be36
AK
1669#ifdef CONFIG_PREEMPT_NOTIFIERS
1670
1671/**
421cee29
RD
1672 * preempt_notifier_register - tell me when current is being being preempted & rescheduled
1673 * @notifier: notifier struct to register
e107be36
AK
1674 */
1675void preempt_notifier_register(struct preempt_notifier *notifier)
1676{
1677 hlist_add_head(&notifier->link, &current->preempt_notifiers);
1678}
1679EXPORT_SYMBOL_GPL(preempt_notifier_register);
1680
1681/**
1682 * preempt_notifier_unregister - no longer interested in preemption notifications
421cee29 1683 * @notifier: notifier struct to unregister
e107be36
AK
1684 *
1685 * This is safe to call from within a preemption notifier.
1686 */
1687void preempt_notifier_unregister(struct preempt_notifier *notifier)
1688{
1689 hlist_del(&notifier->link);
1690}
1691EXPORT_SYMBOL_GPL(preempt_notifier_unregister);
1692
1693static void fire_sched_in_preempt_notifiers(struct task_struct *curr)
1694{
1695 struct preempt_notifier *notifier;
1696 struct hlist_node *node;
1697
1698 hlist_for_each_entry(notifier, node, &curr->preempt_notifiers, link)
1699 notifier->ops->sched_in(notifier, raw_smp_processor_id());
1700}
1701
1702static void
1703fire_sched_out_preempt_notifiers(struct task_struct *curr,
1704 struct task_struct *next)
1705{
1706 struct preempt_notifier *notifier;
1707 struct hlist_node *node;
1708
1709 hlist_for_each_entry(notifier, node, &curr->preempt_notifiers, link)
1710 notifier->ops->sched_out(notifier, next);
1711}
1712
1713#else
1714
1715static void fire_sched_in_preempt_notifiers(struct task_struct *curr)
1716{
1717}
1718
1719static void
1720fire_sched_out_preempt_notifiers(struct task_struct *curr,
1721 struct task_struct *next)
1722{
1723}
1724
1725#endif
1726
4866cde0
NP
1727/**
1728 * prepare_task_switch - prepare to switch tasks
1729 * @rq: the runqueue preparing to switch
421cee29 1730 * @prev: the current task that is being switched out
4866cde0
NP
1731 * @next: the task we are going to switch to.
1732 *
1733 * This is called with the rq lock held and interrupts off. It must
1734 * be paired with a subsequent finish_task_switch after the context
1735 * switch.
1736 *
1737 * prepare_task_switch sets up locking and calls architecture specific
1738 * hooks.
1739 */
e107be36
AK
1740static inline void
1741prepare_task_switch(struct rq *rq, struct task_struct *prev,
1742 struct task_struct *next)
4866cde0 1743{
e107be36 1744 fire_sched_out_preempt_notifiers(prev, next);
4866cde0
NP
1745 prepare_lock_switch(rq, next);
1746 prepare_arch_switch(next);
1747}
1748
1da177e4
LT
1749/**
1750 * finish_task_switch - clean up after a task-switch
344babaa 1751 * @rq: runqueue associated with task-switch
1da177e4
LT
1752 * @prev: the thread we just switched away from.
1753 *
4866cde0
NP
1754 * finish_task_switch must be called after the context switch, paired
1755 * with a prepare_task_switch call before the context switch.
1756 * finish_task_switch will reconcile locking set up by prepare_task_switch,
1757 * and do any other architecture-specific cleanup actions.
1da177e4
LT
1758 *
1759 * Note that we may have delayed dropping an mm in context_switch(). If
1760 * so, we finish that here outside of the runqueue lock. (Doing it
1761 * with the lock held can cause deadlocks; see schedule() for
1762 * details.)
1763 */
70b97a7f 1764static inline void finish_task_switch(struct rq *rq, struct task_struct *prev)
1da177e4
LT
1765 __releases(rq->lock)
1766{
1da177e4 1767 struct mm_struct *mm = rq->prev_mm;
55a101f8 1768 long prev_state;
1da177e4
LT
1769
1770 rq->prev_mm = NULL;
1771
1772 /*
1773 * A task struct has one reference for the use as "current".
c394cc9f 1774 * If a task dies, then it sets TASK_DEAD in tsk->state and calls
55a101f8
ON
1775 * schedule one last time. The schedule call will never return, and
1776 * the scheduled task must drop that reference.
c394cc9f 1777 * The test for TASK_DEAD must occur while the runqueue locks are
1da177e4
LT
1778 * still held, otherwise prev could be scheduled on another cpu, die
1779 * there before we look at prev->state, and then the reference would
1780 * be dropped twice.
1781 * Manfred Spraul <manfred@colorfullife.com>
1782 */
55a101f8 1783 prev_state = prev->state;
4866cde0
NP
1784 finish_arch_switch(prev);
1785 finish_lock_switch(rq, prev);
e107be36 1786 fire_sched_in_preempt_notifiers(current);
1da177e4
LT
1787 if (mm)
1788 mmdrop(mm);
c394cc9f 1789 if (unlikely(prev_state == TASK_DEAD)) {
c6fd91f0 1790 /*
1791 * Remove function-return probe instances associated with this
1792 * task and put them back on the free list.
9761eea8 1793 */
c6fd91f0 1794 kprobe_flush_task(prev);
1da177e4 1795 put_task_struct(prev);
c6fd91f0 1796 }
1da177e4
LT
1797}
1798
1799/**
1800 * schedule_tail - first thing a freshly forked thread must call.
1801 * @prev: the thread we just switched away from.
1802 */
36c8b586 1803asmlinkage void schedule_tail(struct task_struct *prev)
1da177e4
LT
1804 __releases(rq->lock)
1805{
70b97a7f
IM
1806 struct rq *rq = this_rq();
1807
4866cde0
NP
1808 finish_task_switch(rq, prev);
1809#ifdef __ARCH_WANT_UNLOCKED_CTXSW
1810 /* In this case, finish_task_switch does not reenable preemption */
1811 preempt_enable();
1812#endif
1da177e4
LT
1813 if (current->set_child_tid)
1814 put_user(current->pid, current->set_child_tid);
1815}
1816
1817/*
1818 * context_switch - switch to the new MM and the new
1819 * thread's register state.
1820 */
dd41f596 1821static inline void
70b97a7f 1822context_switch(struct rq *rq, struct task_struct *prev,
36c8b586 1823 struct task_struct *next)
1da177e4 1824{
dd41f596 1825 struct mm_struct *mm, *oldmm;
1da177e4 1826
e107be36 1827 prepare_task_switch(rq, prev, next);
dd41f596
IM
1828 mm = next->mm;
1829 oldmm = prev->active_mm;
9226d125
ZA
1830 /*
1831 * For paravirt, this is coupled with an exit in switch_to to
1832 * combine the page table reload and the switch backend into
1833 * one hypercall.
1834 */
1835 arch_enter_lazy_cpu_mode();
1836
dd41f596 1837 if (unlikely(!mm)) {
1da177e4
LT
1838 next->active_mm = oldmm;
1839 atomic_inc(&oldmm->mm_count);
1840 enter_lazy_tlb(oldmm, next);
1841 } else
1842 switch_mm(oldmm, mm, next);
1843
dd41f596 1844 if (unlikely(!prev->mm)) {
1da177e4 1845 prev->active_mm = NULL;
1da177e4
LT
1846 rq->prev_mm = oldmm;
1847 }
3a5f5e48
IM
1848 /*
1849 * Since the runqueue lock will be released by the next
1850 * task (which is an invalid locking op but in the case
1851 * of the scheduler it's an obvious special-case), so we
1852 * do an early lockdep release here:
1853 */
1854#ifndef __ARCH_WANT_UNLOCKED_CTXSW
8a25d5de 1855 spin_release(&rq->lock.dep_map, 1, _THIS_IP_);
3a5f5e48 1856#endif
1da177e4
LT
1857
1858 /* Here we just switch the register state and the stack. */
1859 switch_to(prev, next, prev);
1860
dd41f596
IM
1861 barrier();
1862 /*
1863 * this_rq must be evaluated again because prev may have moved
1864 * CPUs since it called schedule(), thus the 'rq' on its stack
1865 * frame will be invalid.
1866 */
1867 finish_task_switch(this_rq(), prev);
1da177e4
LT
1868}
1869
1870/*
1871 * nr_running, nr_uninterruptible and nr_context_switches:
1872 *
1873 * externally visible scheduler statistics: current number of runnable
1874 * threads, current number of uninterruptible-sleeping threads, total
1875 * number of context switches performed since bootup.
1876 */
1877unsigned long nr_running(void)
1878{
1879 unsigned long i, sum = 0;
1880
1881 for_each_online_cpu(i)
1882 sum += cpu_rq(i)->nr_running;
1883
1884 return sum;
1885}
1886
1887unsigned long nr_uninterruptible(void)
1888{
1889 unsigned long i, sum = 0;
1890
0a945022 1891 for_each_possible_cpu(i)
1da177e4
LT
1892 sum += cpu_rq(i)->nr_uninterruptible;
1893
1894 /*
1895 * Since we read the counters lockless, it might be slightly
1896 * inaccurate. Do not allow it to go below zero though:
1897 */
1898 if (unlikely((long)sum < 0))
1899 sum = 0;
1900
1901 return sum;
1902}
1903
1904unsigned long long nr_context_switches(void)
1905{
cc94abfc
SR
1906 int i;
1907 unsigned long long sum = 0;
1da177e4 1908
0a945022 1909 for_each_possible_cpu(i)
1da177e4
LT
1910 sum += cpu_rq(i)->nr_switches;
1911
1912 return sum;
1913}
1914
1915unsigned long nr_iowait(void)
1916{
1917 unsigned long i, sum = 0;
1918
0a945022 1919 for_each_possible_cpu(i)
1da177e4
LT
1920 sum += atomic_read(&cpu_rq(i)->nr_iowait);
1921
1922 return sum;
1923}
1924
db1b1fef
JS
1925unsigned long nr_active(void)
1926{
1927 unsigned long i, running = 0, uninterruptible = 0;
1928
1929 for_each_online_cpu(i) {
1930 running += cpu_rq(i)->nr_running;
1931 uninterruptible += cpu_rq(i)->nr_uninterruptible;
1932 }
1933
1934 if (unlikely((long)uninterruptible < 0))
1935 uninterruptible = 0;
1936
1937 return running + uninterruptible;
1938}
1939
48f24c4d 1940/*
dd41f596
IM
1941 * Update rq->cpu_load[] statistics. This function is usually called every
1942 * scheduler tick (TICK_NSEC).
48f24c4d 1943 */
dd41f596 1944static void update_cpu_load(struct rq *this_rq)
48f24c4d 1945{
dd41f596
IM
1946 u64 fair_delta64, exec_delta64, idle_delta64, sample_interval64, tmp64;
1947 unsigned long total_load = this_rq->ls.load.weight;
1948 unsigned long this_load = total_load;
1949 struct load_stat *ls = &this_rq->ls;
dd41f596
IM
1950 int i, scale;
1951
c1b3da3e 1952 __update_rq_clock(this_rq);
c1b3da3e 1953
dd41f596
IM
1954 this_rq->nr_load_updates++;
1955 if (unlikely(!(sysctl_sched_features & SCHED_FEAT_PRECISE_CPU_LOAD)))
1956 goto do_avg;
1957
1958 /* Update delta_fair/delta_exec fields first */
84a1d7a2 1959 update_curr_load(this_rq);
dd41f596
IM
1960
1961 fair_delta64 = ls->delta_fair + 1;
1962 ls->delta_fair = 0;
1963
1964 exec_delta64 = ls->delta_exec + 1;
1965 ls->delta_exec = 0;
1966
d281918d
IM
1967 sample_interval64 = this_rq->clock - ls->load_update_last;
1968 ls->load_update_last = this_rq->clock;
dd41f596
IM
1969
1970 if ((s64)sample_interval64 < (s64)TICK_NSEC)
1971 sample_interval64 = TICK_NSEC;
1972
1973 if (exec_delta64 > sample_interval64)
1974 exec_delta64 = sample_interval64;
1975
1976 idle_delta64 = sample_interval64 - exec_delta64;
1977
1978 tmp64 = div64_64(SCHED_LOAD_SCALE * exec_delta64, fair_delta64);
1979 tmp64 = div64_64(tmp64 * exec_delta64, sample_interval64);
1980
1981 this_load = (unsigned long)tmp64;
1982
1983do_avg:
1984
1985 /* Update our load: */
1986 for (i = 0, scale = 1; i < CPU_LOAD_IDX_MAX; i++, scale += scale) {
1987 unsigned long old_load, new_load;
1988
1989 /* scale is effectively 1 << i now, and >> i divides by scale */
1990
1991 old_load = this_rq->cpu_load[i];
1992 new_load = this_load;
1993
1994 this_rq->cpu_load[i] = (old_load*(scale-1) + new_load) >> i;
1995 }
48f24c4d
IM
1996}
1997
dd41f596
IM
1998#ifdef CONFIG_SMP
1999
1da177e4
LT
2000/*
2001 * double_rq_lock - safely lock two runqueues
2002 *
2003 * Note this does not disable interrupts like task_rq_lock,
2004 * you need to do so manually before calling.
2005 */
70b97a7f 2006static void double_rq_lock(struct rq *rq1, struct rq *rq2)
1da177e4
LT
2007 __acquires(rq1->lock)
2008 __acquires(rq2->lock)
2009{
054b9108 2010 BUG_ON(!irqs_disabled());
1da177e4
LT
2011 if (rq1 == rq2) {
2012 spin_lock(&rq1->lock);
2013 __acquire(rq2->lock); /* Fake it out ;) */
2014 } else {
c96d145e 2015 if (rq1 < rq2) {
1da177e4
LT
2016 spin_lock(&rq1->lock);
2017 spin_lock(&rq2->lock);
2018 } else {
2019 spin_lock(&rq2->lock);
2020 spin_lock(&rq1->lock);
2021 }
2022 }
2023}
2024
2025/*
2026 * double_rq_unlock - safely unlock two runqueues
2027 *
2028 * Note this does not restore interrupts like task_rq_unlock,
2029 * you need to do so manually after calling.
2030 */
70b97a7f 2031static void double_rq_unlock(struct rq *rq1, struct rq *rq2)
1da177e4
LT
2032 __releases(rq1->lock)
2033 __releases(rq2->lock)
2034{
2035 spin_unlock(&rq1->lock);
2036 if (rq1 != rq2)
2037 spin_unlock(&rq2->lock);
2038 else
2039 __release(rq2->lock);
2040}
2041
2042/*
2043 * double_lock_balance - lock the busiest runqueue, this_rq is locked already.
2044 */
70b97a7f 2045static void double_lock_balance(struct rq *this_rq, struct rq *busiest)
1da177e4
LT
2046 __releases(this_rq->lock)
2047 __acquires(busiest->lock)
2048 __acquires(this_rq->lock)
2049{
054b9108
KK
2050 if (unlikely(!irqs_disabled())) {
2051 /* printk() doesn't work good under rq->lock */
2052 spin_unlock(&this_rq->lock);
2053 BUG_ON(1);
2054 }
1da177e4 2055 if (unlikely(!spin_trylock(&busiest->lock))) {
c96d145e 2056 if (busiest < this_rq) {
1da177e4
LT
2057 spin_unlock(&this_rq->lock);
2058 spin_lock(&busiest->lock);
2059 spin_lock(&this_rq->lock);
2060 } else
2061 spin_lock(&busiest->lock);
2062 }
2063}
2064
1da177e4
LT
2065/*
2066 * If dest_cpu is allowed for this process, migrate the task to it.
2067 * This is accomplished by forcing the cpu_allowed mask to only
2068 * allow dest_cpu, which will force the cpu onto dest_cpu. Then
2069 * the cpu_allowed mask is restored.
2070 */
36c8b586 2071static void sched_migrate_task(struct task_struct *p, int dest_cpu)
1da177e4 2072{
70b97a7f 2073 struct migration_req req;
1da177e4 2074 unsigned long flags;
70b97a7f 2075 struct rq *rq;
1da177e4
LT
2076
2077 rq = task_rq_lock(p, &flags);
2078 if (!cpu_isset(dest_cpu, p->cpus_allowed)
2079 || unlikely(cpu_is_offline(dest_cpu)))
2080 goto out;
2081
2082 /* force the process onto the specified CPU */
2083 if (migrate_task(p, dest_cpu, &req)) {
2084 /* Need to wait for migration thread (might exit: take ref). */
2085 struct task_struct *mt = rq->migration_thread;
36c8b586 2086
1da177e4
LT
2087 get_task_struct(mt);
2088 task_rq_unlock(rq, &flags);
2089 wake_up_process(mt);
2090 put_task_struct(mt);
2091 wait_for_completion(&req.done);
36c8b586 2092
1da177e4
LT
2093 return;
2094 }
2095out:
2096 task_rq_unlock(rq, &flags);
2097}
2098
2099/*
476d139c
NP
2100 * sched_exec - execve() is a valuable balancing opportunity, because at
2101 * this point the task has the smallest effective memory and cache footprint.
1da177e4
LT
2102 */
2103void sched_exec(void)
2104{
1da177e4 2105 int new_cpu, this_cpu = get_cpu();
476d139c 2106 new_cpu = sched_balance_self(this_cpu, SD_BALANCE_EXEC);
1da177e4 2107 put_cpu();
476d139c
NP
2108 if (new_cpu != this_cpu)
2109 sched_migrate_task(current, new_cpu);
1da177e4
LT
2110}
2111
2112/*
2113 * pull_task - move a task from a remote runqueue to the local runqueue.
2114 * Both runqueues must be locked.
2115 */
dd41f596
IM
2116static void pull_task(struct rq *src_rq, struct task_struct *p,
2117 struct rq *this_rq, int this_cpu)
1da177e4 2118{
a8e504d2 2119 update_rq_clock(src_rq);
2e1cb74a 2120 deactivate_task(src_rq, p, 0);
1da177e4 2121 set_task_cpu(p, this_cpu);
dd41f596 2122 activate_task(this_rq, p, 0);
1da177e4
LT
2123 /*
2124 * Note that idle threads have a prio of MAX_PRIO, for this test
2125 * to be always true for them.
2126 */
dd41f596 2127 check_preempt_curr(this_rq, p);
1da177e4
LT
2128}
2129
2130/*
2131 * can_migrate_task - may task p from runqueue rq be migrated to this_cpu?
2132 */
858119e1 2133static
70b97a7f 2134int can_migrate_task(struct task_struct *p, struct rq *rq, int this_cpu,
d15bcfdb 2135 struct sched_domain *sd, enum cpu_idle_type idle,
95cdf3b7 2136 int *all_pinned)
1da177e4
LT
2137{
2138 /*
2139 * We do not migrate tasks that are:
2140 * 1) running (obviously), or
2141 * 2) cannot be migrated to this CPU due to cpus_allowed, or
2142 * 3) are cache-hot on their current CPU.
2143 */
1da177e4
LT
2144 if (!cpu_isset(this_cpu, p->cpus_allowed))
2145 return 0;
81026794
NP
2146 *all_pinned = 0;
2147
2148 if (task_running(rq, p))
2149 return 0;
1da177e4
LT
2150
2151 /*
dd41f596 2152 * Aggressive migration if too many balance attempts have failed:
1da177e4 2153 */
dd41f596 2154 if (sd->nr_balance_failed > sd->cache_nice_tries)
1da177e4
LT
2155 return 1;
2156
1da177e4
LT
2157 return 1;
2158}
2159
dd41f596 2160static int balance_tasks(struct rq *this_rq, int this_cpu, struct rq *busiest,
2dd73a4f 2161 unsigned long max_nr_move, unsigned long max_load_move,
d15bcfdb 2162 struct sched_domain *sd, enum cpu_idle_type idle,
dd41f596 2163 int *all_pinned, unsigned long *load_moved,
a4ac01c3 2164 int *this_best_prio, struct rq_iterator *iterator)
1da177e4 2165{
dd41f596
IM
2166 int pulled = 0, pinned = 0, skip_for_load;
2167 struct task_struct *p;
2168 long rem_load_move = max_load_move;
1da177e4 2169
2dd73a4f 2170 if (max_nr_move == 0 || max_load_move == 0)
1da177e4
LT
2171 goto out;
2172
81026794
NP
2173 pinned = 1;
2174
1da177e4 2175 /*
dd41f596 2176 * Start the load-balancing iterator:
1da177e4 2177 */
dd41f596
IM
2178 p = iterator->start(iterator->arg);
2179next:
2180 if (!p)
1da177e4 2181 goto out;
50ddd969
PW
2182 /*
2183 * To help distribute high priority tasks accross CPUs we don't
2184 * skip a task if it will be the highest priority task (i.e. smallest
2185 * prio value) on its new queue regardless of its load weight
2186 */
dd41f596
IM
2187 skip_for_load = (p->se.load.weight >> 1) > rem_load_move +
2188 SCHED_LOAD_SCALE_FUZZ;
a4ac01c3 2189 if ((skip_for_load && p->prio >= *this_best_prio) ||
dd41f596 2190 !can_migrate_task(p, busiest, this_cpu, sd, idle, &pinned)) {
dd41f596
IM
2191 p = iterator->next(iterator->arg);
2192 goto next;
1da177e4
LT
2193 }
2194
dd41f596 2195 pull_task(busiest, p, this_rq, this_cpu);
1da177e4 2196 pulled++;
dd41f596 2197 rem_load_move -= p->se.load.weight;
1da177e4 2198
2dd73a4f
PW
2199 /*
2200 * We only want to steal up to the prescribed number of tasks
2201 * and the prescribed amount of weighted load.
2202 */
2203 if (pulled < max_nr_move && rem_load_move > 0) {
a4ac01c3
PW
2204 if (p->prio < *this_best_prio)
2205 *this_best_prio = p->prio;
dd41f596
IM
2206 p = iterator->next(iterator->arg);
2207 goto next;
1da177e4
LT
2208 }
2209out:
2210 /*
2211 * Right now, this is the only place pull_task() is called,
2212 * so we can safely collect pull_task() stats here rather than
2213 * inside pull_task().
2214 */
2215 schedstat_add(sd, lb_gained[idle], pulled);
81026794
NP
2216
2217 if (all_pinned)
2218 *all_pinned = pinned;
dd41f596 2219 *load_moved = max_load_move - rem_load_move;
1da177e4
LT
2220 return pulled;
2221}
2222
dd41f596 2223/*
43010659
PW
2224 * move_tasks tries to move up to max_load_move weighted load from busiest to
2225 * this_rq, as part of a balancing operation within domain "sd".
2226 * Returns 1 if successful and 0 otherwise.
dd41f596
IM
2227 *
2228 * Called with both runqueues locked.
2229 */
2230static int move_tasks(struct rq *this_rq, int this_cpu, struct rq *busiest,
43010659 2231 unsigned long max_load_move,
dd41f596
IM
2232 struct sched_domain *sd, enum cpu_idle_type idle,
2233 int *all_pinned)
2234{
2235 struct sched_class *class = sched_class_highest;
43010659 2236 unsigned long total_load_moved = 0;
a4ac01c3 2237 int this_best_prio = this_rq->curr->prio;
dd41f596
IM
2238
2239 do {
43010659
PW
2240 total_load_moved +=
2241 class->load_balance(this_rq, this_cpu, busiest,
2242 ULONG_MAX, max_load_move - total_load_moved,
a4ac01c3 2243 sd, idle, all_pinned, &this_best_prio);
dd41f596 2244 class = class->next;
43010659 2245 } while (class && max_load_move > total_load_moved);
dd41f596 2246
43010659
PW
2247 return total_load_moved > 0;
2248}
2249
2250/*
2251 * move_one_task tries to move exactly one task from busiest to this_rq, as
2252 * part of active balancing operations within "domain".
2253 * Returns 1 if successful and 0 otherwise.
2254 *
2255 * Called with both runqueues locked.
2256 */
2257static int move_one_task(struct rq *this_rq, int this_cpu, struct rq *busiest,
2258 struct sched_domain *sd, enum cpu_idle_type idle)
2259{
2260 struct sched_class *class;
a4ac01c3 2261 int this_best_prio = MAX_PRIO;
43010659
PW
2262
2263 for (class = sched_class_highest; class; class = class->next)
2264 if (class->load_balance(this_rq, this_cpu, busiest,
a4ac01c3
PW
2265 1, ULONG_MAX, sd, idle, NULL,
2266 &this_best_prio))
43010659
PW
2267 return 1;
2268
2269 return 0;
dd41f596
IM
2270}
2271
1da177e4
LT
2272/*
2273 * find_busiest_group finds and returns the busiest CPU group within the
48f24c4d
IM
2274 * domain. It calculates and returns the amount of weighted load which
2275 * should be moved to restore balance via the imbalance parameter.
1da177e4
LT
2276 */
2277static struct sched_group *
2278find_busiest_group(struct sched_domain *sd, int this_cpu,
dd41f596
IM
2279 unsigned long *imbalance, enum cpu_idle_type idle,
2280 int *sd_idle, cpumask_t *cpus, int *balance)
1da177e4
LT
2281{
2282 struct sched_group *busiest = NULL, *this = NULL, *group = sd->groups;
2283 unsigned long max_load, avg_load, total_load, this_load, total_pwr;
0c117f1b 2284 unsigned long max_pull;
2dd73a4f
PW
2285 unsigned long busiest_load_per_task, busiest_nr_running;
2286 unsigned long this_load_per_task, this_nr_running;
7897986b 2287 int load_idx;
5c45bf27
SS
2288#if defined(CONFIG_SCHED_MC) || defined(CONFIG_SCHED_SMT)
2289 int power_savings_balance = 1;
2290 unsigned long leader_nr_running = 0, min_load_per_task = 0;
2291 unsigned long min_nr_running = ULONG_MAX;
2292 struct sched_group *group_min = NULL, *group_leader = NULL;
2293#endif
1da177e4
LT
2294
2295 max_load = this_load = total_load = total_pwr = 0;
2dd73a4f
PW
2296 busiest_load_per_task = busiest_nr_running = 0;
2297 this_load_per_task = this_nr_running = 0;
d15bcfdb 2298 if (idle == CPU_NOT_IDLE)
7897986b 2299 load_idx = sd->busy_idx;
d15bcfdb 2300 else if (idle == CPU_NEWLY_IDLE)
7897986b
NP
2301 load_idx = sd->newidle_idx;
2302 else
2303 load_idx = sd->idle_idx;
1da177e4
LT
2304
2305 do {
5c45bf27 2306 unsigned long load, group_capacity;
1da177e4
LT
2307 int local_group;
2308 int i;
783609c6 2309 unsigned int balance_cpu = -1, first_idle_cpu = 0;
2dd73a4f 2310 unsigned long sum_nr_running, sum_weighted_load;
1da177e4
LT
2311
2312 local_group = cpu_isset(this_cpu, group->cpumask);
2313
783609c6
SS
2314 if (local_group)
2315 balance_cpu = first_cpu(group->cpumask);
2316
1da177e4 2317 /* Tally up the load of all CPUs in the group */
2dd73a4f 2318 sum_weighted_load = sum_nr_running = avg_load = 0;
1da177e4
LT
2319
2320 for_each_cpu_mask(i, group->cpumask) {
0a2966b4
CL
2321 struct rq *rq;
2322
2323 if (!cpu_isset(i, *cpus))
2324 continue;
2325
2326 rq = cpu_rq(i);
2dd73a4f 2327
9439aab8 2328 if (*sd_idle && rq->nr_running)
5969fe06
NP
2329 *sd_idle = 0;
2330
1da177e4 2331 /* Bias balancing toward cpus of our domain */
783609c6
SS
2332 if (local_group) {
2333 if (idle_cpu(i) && !first_idle_cpu) {
2334 first_idle_cpu = 1;
2335 balance_cpu = i;
2336 }
2337
a2000572 2338 load = target_load(i, load_idx);
783609c6 2339 } else
a2000572 2340 load = source_load(i, load_idx);
1da177e4
LT
2341
2342 avg_load += load;
2dd73a4f 2343 sum_nr_running += rq->nr_running;
dd41f596 2344 sum_weighted_load += weighted_cpuload(i);
1da177e4
LT
2345 }
2346
783609c6
SS
2347 /*
2348 * First idle cpu or the first cpu(busiest) in this sched group
2349 * is eligible for doing load balancing at this and above
9439aab8
SS
2350 * domains. In the newly idle case, we will allow all the cpu's
2351 * to do the newly idle load balance.
783609c6 2352 */
9439aab8
SS
2353 if (idle != CPU_NEWLY_IDLE && local_group &&
2354 balance_cpu != this_cpu && balance) {
783609c6
SS
2355 *balance = 0;
2356 goto ret;
2357 }
2358
1da177e4 2359 total_load += avg_load;
5517d86b 2360 total_pwr += group->__cpu_power;
1da177e4
LT
2361
2362 /* Adjust by relative CPU power of the group */
5517d86b
ED
2363 avg_load = sg_div_cpu_power(group,
2364 avg_load * SCHED_LOAD_SCALE);
1da177e4 2365
5517d86b 2366 group_capacity = group->__cpu_power / SCHED_LOAD_SCALE;
5c45bf27 2367
1da177e4
LT
2368 if (local_group) {
2369 this_load = avg_load;
2370 this = group;
2dd73a4f
PW
2371 this_nr_running = sum_nr_running;
2372 this_load_per_task = sum_weighted_load;
2373 } else if (avg_load > max_load &&
5c45bf27 2374 sum_nr_running > group_capacity) {
1da177e4
LT
2375 max_load = avg_load;
2376 busiest = group;
2dd73a4f
PW
2377 busiest_nr_running = sum_nr_running;
2378 busiest_load_per_task = sum_weighted_load;
1da177e4 2379 }
5c45bf27
SS
2380
2381#if defined(CONFIG_SCHED_MC) || defined(CONFIG_SCHED_SMT)
2382 /*
2383 * Busy processors will not participate in power savings
2384 * balance.
2385 */
dd41f596
IM
2386 if (idle == CPU_NOT_IDLE ||
2387 !(sd->flags & SD_POWERSAVINGS_BALANCE))
2388 goto group_next;
5c45bf27
SS
2389
2390 /*
2391 * If the local group is idle or completely loaded
2392 * no need to do power savings balance at this domain
2393 */
2394 if (local_group && (this_nr_running >= group_capacity ||
2395 !this_nr_running))
2396 power_savings_balance = 0;
2397
dd41f596 2398 /*
5c45bf27
SS
2399 * If a group is already running at full capacity or idle,
2400 * don't include that group in power savings calculations
dd41f596
IM
2401 */
2402 if (!power_savings_balance || sum_nr_running >= group_capacity
5c45bf27 2403 || !sum_nr_running)
dd41f596 2404 goto group_next;
5c45bf27 2405
dd41f596 2406 /*
5c45bf27 2407 * Calculate the group which has the least non-idle load.
dd41f596
IM
2408 * This is the group from where we need to pick up the load
2409 * for saving power
2410 */
2411 if ((sum_nr_running < min_nr_running) ||
2412 (sum_nr_running == min_nr_running &&
5c45bf27
SS
2413 first_cpu(group->cpumask) <
2414 first_cpu(group_min->cpumask))) {
dd41f596
IM
2415 group_min = group;
2416 min_nr_running = sum_nr_running;
5c45bf27
SS
2417 min_load_per_task = sum_weighted_load /
2418 sum_nr_running;
dd41f596 2419 }
5c45bf27 2420
dd41f596 2421 /*
5c45bf27 2422 * Calculate the group which is almost near its
dd41f596
IM
2423 * capacity but still has some space to pick up some load
2424 * from other group and save more power
2425 */
2426 if (sum_nr_running <= group_capacity - 1) {
2427 if (sum_nr_running > leader_nr_running ||
2428 (sum_nr_running == leader_nr_running &&
2429 first_cpu(group->cpumask) >
2430 first_cpu(group_leader->cpumask))) {
2431 group_leader = group;
2432 leader_nr_running = sum_nr_running;
2433 }
48f24c4d 2434 }
5c45bf27
SS
2435group_next:
2436#endif
1da177e4
LT
2437 group = group->next;
2438 } while (group != sd->groups);
2439
2dd73a4f 2440 if (!busiest || this_load >= max_load || busiest_nr_running == 0)
1da177e4
LT
2441 goto out_balanced;
2442
2443 avg_load = (SCHED_LOAD_SCALE * total_load) / total_pwr;
2444
2445 if (this_load >= avg_load ||
2446 100*max_load <= sd->imbalance_pct*this_load)
2447 goto out_balanced;
2448
2dd73a4f 2449 busiest_load_per_task /= busiest_nr_running;
1da177e4
LT
2450 /*
2451 * We're trying to get all the cpus to the average_load, so we don't
2452 * want to push ourselves above the average load, nor do we wish to
2453 * reduce the max loaded cpu below the average load, as either of these
2454 * actions would just result in more rebalancing later, and ping-pong
2455 * tasks around. Thus we look for the minimum possible imbalance.
2456 * Negative imbalances (*we* are more loaded than anyone else) will
2457 * be counted as no imbalance for these purposes -- we can't fix that
2458 * by pulling tasks to us. Be careful of negative numbers as they'll
2459 * appear as very large values with unsigned longs.
2460 */
2dd73a4f
PW
2461 if (max_load <= busiest_load_per_task)
2462 goto out_balanced;
2463
2464 /*
2465 * In the presence of smp nice balancing, certain scenarios can have
2466 * max load less than avg load(as we skip the groups at or below
2467 * its cpu_power, while calculating max_load..)
2468 */
2469 if (max_load < avg_load) {
2470 *imbalance = 0;
2471 goto small_imbalance;
2472 }
0c117f1b
SS
2473
2474 /* Don't want to pull so many tasks that a group would go idle */
2dd73a4f 2475 max_pull = min(max_load - avg_load, max_load - busiest_load_per_task);
0c117f1b 2476
1da177e4 2477 /* How much load to actually move to equalise the imbalance */
5517d86b
ED
2478 *imbalance = min(max_pull * busiest->__cpu_power,
2479 (avg_load - this_load) * this->__cpu_power)
1da177e4
LT
2480 / SCHED_LOAD_SCALE;
2481
2dd73a4f
PW
2482 /*
2483 * if *imbalance is less than the average load per runnable task
2484 * there is no gaurantee that any tasks will be moved so we'll have
2485 * a think about bumping its value to force at least one task to be
2486 * moved
2487 */
dd41f596 2488 if (*imbalance + SCHED_LOAD_SCALE_FUZZ < busiest_load_per_task/2) {
48f24c4d 2489 unsigned long tmp, pwr_now, pwr_move;
2dd73a4f
PW
2490 unsigned int imbn;
2491
2492small_imbalance:
2493 pwr_move = pwr_now = 0;
2494 imbn = 2;
2495 if (this_nr_running) {
2496 this_load_per_task /= this_nr_running;
2497 if (busiest_load_per_task > this_load_per_task)
2498 imbn = 1;
2499 } else
2500 this_load_per_task = SCHED_LOAD_SCALE;
1da177e4 2501
dd41f596
IM
2502 if (max_load - this_load + SCHED_LOAD_SCALE_FUZZ >=
2503 busiest_load_per_task * imbn) {
2dd73a4f 2504 *imbalance = busiest_load_per_task;
1da177e4
LT
2505 return busiest;
2506 }
2507
2508 /*
2509 * OK, we don't have enough imbalance to justify moving tasks,
2510 * however we may be able to increase total CPU power used by
2511 * moving them.
2512 */
2513
5517d86b
ED
2514 pwr_now += busiest->__cpu_power *
2515 min(busiest_load_per_task, max_load);
2516 pwr_now += this->__cpu_power *
2517 min(this_load_per_task, this_load);
1da177e4
LT
2518 pwr_now /= SCHED_LOAD_SCALE;
2519
2520 /* Amount of load we'd subtract */
5517d86b
ED
2521 tmp = sg_div_cpu_power(busiest,
2522 busiest_load_per_task * SCHED_LOAD_SCALE);
1da177e4 2523 if (max_load > tmp)
5517d86b 2524 pwr_move += busiest->__cpu_power *
2dd73a4f 2525 min(busiest_load_per_task, max_load - tmp);
1da177e4
LT
2526
2527 /* Amount of load we'd add */
5517d86b 2528 if (max_load * busiest->__cpu_power <
33859f7f 2529 busiest_load_per_task * SCHED_LOAD_SCALE)
5517d86b
ED
2530 tmp = sg_div_cpu_power(this,
2531 max_load * busiest->__cpu_power);
1da177e4 2532 else
5517d86b
ED
2533 tmp = sg_div_cpu_power(this,
2534 busiest_load_per_task * SCHED_LOAD_SCALE);
2535 pwr_move += this->__cpu_power *
2536 min(this_load_per_task, this_load + tmp);
1da177e4
LT
2537 pwr_move /= SCHED_LOAD_SCALE;
2538
2539 /* Move if we gain throughput */
2540 if (pwr_move <= pwr_now)
2541 goto out_balanced;
2542
2dd73a4f 2543 *imbalance = busiest_load_per_task;
1da177e4
LT
2544 }
2545
1da177e4
LT
2546 return busiest;
2547
2548out_balanced:
5c45bf27 2549#if defined(CONFIG_SCHED_MC) || defined(CONFIG_SCHED_SMT)
d15bcfdb 2550 if (idle == CPU_NOT_IDLE || !(sd->flags & SD_POWERSAVINGS_BALANCE))
5c45bf27 2551 goto ret;
1da177e4 2552
5c45bf27
SS
2553 if (this == group_leader && group_leader != group_min) {
2554 *imbalance = min_load_per_task;
2555 return group_min;
2556 }
5c45bf27 2557#endif
783609c6 2558ret:
1da177e4
LT
2559 *imbalance = 0;
2560 return NULL;
2561}
2562
2563/*
2564 * find_busiest_queue - find the busiest runqueue among the cpus in group.
2565 */
70b97a7f 2566static struct rq *
d15bcfdb 2567find_busiest_queue(struct sched_group *group, enum cpu_idle_type idle,
0a2966b4 2568 unsigned long imbalance, cpumask_t *cpus)
1da177e4 2569{
70b97a7f 2570 struct rq *busiest = NULL, *rq;
2dd73a4f 2571 unsigned long max_load = 0;
1da177e4
LT
2572 int i;
2573
2574 for_each_cpu_mask(i, group->cpumask) {
dd41f596 2575 unsigned long wl;
0a2966b4
CL
2576
2577 if (!cpu_isset(i, *cpus))
2578 continue;
2579
48f24c4d 2580 rq = cpu_rq(i);
dd41f596 2581 wl = weighted_cpuload(i);
2dd73a4f 2582
dd41f596 2583 if (rq->nr_running == 1 && wl > imbalance)
2dd73a4f 2584 continue;
1da177e4 2585
dd41f596
IM
2586 if (wl > max_load) {
2587 max_load = wl;
48f24c4d 2588 busiest = rq;
1da177e4
LT
2589 }
2590 }
2591
2592 return busiest;
2593}
2594
77391d71
NP
2595/*
2596 * Max backoff if we encounter pinned tasks. Pretty arbitrary value, but
2597 * so long as it is large enough.
2598 */
2599#define MAX_PINNED_INTERVAL 512
2600
1da177e4
LT
2601/*
2602 * Check this_cpu to ensure it is balanced within domain. Attempt to move
2603 * tasks if there is an imbalance.
1da177e4 2604 */
70b97a7f 2605static int load_balance(int this_cpu, struct rq *this_rq,
d15bcfdb 2606 struct sched_domain *sd, enum cpu_idle_type idle,
783609c6 2607 int *balance)
1da177e4 2608{
43010659 2609 int ld_moved, all_pinned = 0, active_balance = 0, sd_idle = 0;
1da177e4 2610 struct sched_group *group;
1da177e4 2611 unsigned long imbalance;
70b97a7f 2612 struct rq *busiest;
0a2966b4 2613 cpumask_t cpus = CPU_MASK_ALL;
fe2eea3f 2614 unsigned long flags;
5969fe06 2615
89c4710e
SS
2616 /*
2617 * When power savings policy is enabled for the parent domain, idle
2618 * sibling can pick up load irrespective of busy siblings. In this case,
dd41f596 2619 * let the state of idle sibling percolate up as CPU_IDLE, instead of
d15bcfdb 2620 * portraying it as CPU_NOT_IDLE.
89c4710e 2621 */
d15bcfdb 2622 if (idle != CPU_NOT_IDLE && sd->flags & SD_SHARE_CPUPOWER &&
89c4710e 2623 !test_sd_parent(sd, SD_POWERSAVINGS_BALANCE))
5969fe06 2624 sd_idle = 1;
1da177e4 2625
1da177e4
LT
2626 schedstat_inc(sd, lb_cnt[idle]);
2627
0a2966b4
CL
2628redo:
2629 group = find_busiest_group(sd, this_cpu, &imbalance, idle, &sd_idle,
783609c6
SS
2630 &cpus, balance);
2631
06066714 2632 if (*balance == 0)
783609c6 2633 goto out_balanced;
783609c6 2634
1da177e4
LT
2635 if (!group) {
2636 schedstat_inc(sd, lb_nobusyg[idle]);
2637 goto out_balanced;
2638 }
2639
0a2966b4 2640 busiest = find_busiest_queue(group, idle, imbalance, &cpus);
1da177e4
LT
2641 if (!busiest) {
2642 schedstat_inc(sd, lb_nobusyq[idle]);
2643 goto out_balanced;
2644 }
2645
db935dbd 2646 BUG_ON(busiest == this_rq);
1da177e4
LT
2647
2648 schedstat_add(sd, lb_imbalance[idle], imbalance);
2649
43010659 2650 ld_moved = 0;
1da177e4
LT
2651 if (busiest->nr_running > 1) {
2652 /*
2653 * Attempt to move tasks. If find_busiest_group has found
2654 * an imbalance but busiest->nr_running <= 1, the group is
43010659 2655 * still unbalanced. ld_moved simply stays zero, so it is
1da177e4
LT
2656 * correctly treated as an imbalance.
2657 */
fe2eea3f 2658 local_irq_save(flags);
e17224bf 2659 double_rq_lock(this_rq, busiest);
43010659 2660 ld_moved = move_tasks(this_rq, this_cpu, busiest,
48f24c4d 2661 imbalance, sd, idle, &all_pinned);
e17224bf 2662 double_rq_unlock(this_rq, busiest);
fe2eea3f 2663 local_irq_restore(flags);
81026794 2664
46cb4b7c
SS
2665 /*
2666 * some other cpu did the load balance for us.
2667 */
43010659 2668 if (ld_moved && this_cpu != smp_processor_id())
46cb4b7c
SS
2669 resched_cpu(this_cpu);
2670
81026794 2671 /* All tasks on this runqueue were pinned by CPU affinity */
0a2966b4
CL
2672 if (unlikely(all_pinned)) {
2673 cpu_clear(cpu_of(busiest), cpus);
2674 if (!cpus_empty(cpus))
2675 goto redo;
81026794 2676 goto out_balanced;
0a2966b4 2677 }
1da177e4 2678 }
81026794 2679
43010659 2680 if (!ld_moved) {
1da177e4
LT
2681 schedstat_inc(sd, lb_failed[idle]);
2682 sd->nr_balance_failed++;
2683
2684 if (unlikely(sd->nr_balance_failed > sd->cache_nice_tries+2)) {
1da177e4 2685
fe2eea3f 2686 spin_lock_irqsave(&busiest->lock, flags);
fa3b6ddc
SS
2687
2688 /* don't kick the migration_thread, if the curr
2689 * task on busiest cpu can't be moved to this_cpu
2690 */
2691 if (!cpu_isset(this_cpu, busiest->curr->cpus_allowed)) {
fe2eea3f 2692 spin_unlock_irqrestore(&busiest->lock, flags);
fa3b6ddc
SS
2693 all_pinned = 1;
2694 goto out_one_pinned;
2695 }
2696
1da177e4
LT
2697 if (!busiest->active_balance) {
2698 busiest->active_balance = 1;
2699 busiest->push_cpu = this_cpu;
81026794 2700 active_balance = 1;
1da177e4 2701 }
fe2eea3f 2702 spin_unlock_irqrestore(&busiest->lock, flags);
81026794 2703 if (active_balance)
1da177e4
LT
2704 wake_up_process(busiest->migration_thread);
2705
2706 /*
2707 * We've kicked active balancing, reset the failure
2708 * counter.
2709 */
39507451 2710 sd->nr_balance_failed = sd->cache_nice_tries+1;
1da177e4 2711 }
81026794 2712 } else
1da177e4
LT
2713 sd->nr_balance_failed = 0;
2714
81026794 2715 if (likely(!active_balance)) {
1da177e4
LT
2716 /* We were unbalanced, so reset the balancing interval */
2717 sd->balance_interval = sd->min_interval;
81026794
NP
2718 } else {
2719 /*
2720 * If we've begun active balancing, start to back off. This
2721 * case may not be covered by the all_pinned logic if there
2722 * is only 1 task on the busy runqueue (because we don't call
2723 * move_tasks).
2724 */
2725 if (sd->balance_interval < sd->max_interval)
2726 sd->balance_interval *= 2;
1da177e4
LT
2727 }
2728
43010659 2729 if (!ld_moved && !sd_idle && sd->flags & SD_SHARE_CPUPOWER &&
89c4710e 2730 !test_sd_parent(sd, SD_POWERSAVINGS_BALANCE))
5969fe06 2731 return -1;
43010659 2732 return ld_moved;
1da177e4
LT
2733
2734out_balanced:
1da177e4
LT
2735 schedstat_inc(sd, lb_balanced[idle]);
2736
16cfb1c0 2737 sd->nr_balance_failed = 0;
fa3b6ddc
SS
2738
2739out_one_pinned:
1da177e4 2740 /* tune up the balancing interval */
77391d71
NP
2741 if ((all_pinned && sd->balance_interval < MAX_PINNED_INTERVAL) ||
2742 (sd->balance_interval < sd->max_interval))
1da177e4
LT
2743 sd->balance_interval *= 2;
2744
48f24c4d 2745 if (!sd_idle && sd->flags & SD_SHARE_CPUPOWER &&
89c4710e 2746 !test_sd_parent(sd, SD_POWERSAVINGS_BALANCE))
5969fe06 2747 return -1;
1da177e4
LT
2748 return 0;
2749}
2750
2751/*
2752 * Check this_cpu to ensure it is balanced within domain. Attempt to move
2753 * tasks if there is an imbalance.
2754 *
d15bcfdb 2755 * Called from schedule when this_rq is about to become idle (CPU_NEWLY_IDLE).
1da177e4
LT
2756 * this_rq is locked.
2757 */
48f24c4d 2758static int
70b97a7f 2759load_balance_newidle(int this_cpu, struct rq *this_rq, struct sched_domain *sd)
1da177e4
LT
2760{
2761 struct sched_group *group;
70b97a7f 2762 struct rq *busiest = NULL;
1da177e4 2763 unsigned long imbalance;
43010659 2764 int ld_moved = 0;
5969fe06 2765 int sd_idle = 0;
969bb4e4 2766 int all_pinned = 0;
0a2966b4 2767 cpumask_t cpus = CPU_MASK_ALL;
5969fe06 2768
89c4710e
SS
2769 /*
2770 * When power savings policy is enabled for the parent domain, idle
2771 * sibling can pick up load irrespective of busy siblings. In this case,
2772 * let the state of idle sibling percolate up as IDLE, instead of
d15bcfdb 2773 * portraying it as CPU_NOT_IDLE.
89c4710e
SS
2774 */
2775 if (sd->flags & SD_SHARE_CPUPOWER &&
2776 !test_sd_parent(sd, SD_POWERSAVINGS_BALANCE))
5969fe06 2777 sd_idle = 1;
1da177e4 2778
d15bcfdb 2779 schedstat_inc(sd, lb_cnt[CPU_NEWLY_IDLE]);
0a2966b4 2780redo:
d15bcfdb 2781 group = find_busiest_group(sd, this_cpu, &imbalance, CPU_NEWLY_IDLE,
783609c6 2782 &sd_idle, &cpus, NULL);
1da177e4 2783 if (!group) {
d15bcfdb 2784 schedstat_inc(sd, lb_nobusyg[CPU_NEWLY_IDLE]);
16cfb1c0 2785 goto out_balanced;
1da177e4
LT
2786 }
2787
d15bcfdb 2788 busiest = find_busiest_queue(group, CPU_NEWLY_IDLE, imbalance,
0a2966b4 2789 &cpus);
db935dbd 2790 if (!busiest) {
d15bcfdb 2791 schedstat_inc(sd, lb_nobusyq[CPU_NEWLY_IDLE]);
16cfb1c0 2792 goto out_balanced;
1da177e4
LT
2793 }
2794
db935dbd
NP
2795 BUG_ON(busiest == this_rq);
2796
d15bcfdb 2797 schedstat_add(sd, lb_imbalance[CPU_NEWLY_IDLE], imbalance);
d6d5cfaf 2798
43010659 2799 ld_moved = 0;
d6d5cfaf
NP
2800 if (busiest->nr_running > 1) {
2801 /* Attempt to move tasks */
2802 double_lock_balance(this_rq, busiest);
43010659 2803 ld_moved = move_tasks(this_rq, this_cpu, busiest,
969bb4e4
SS
2804 imbalance, sd, CPU_NEWLY_IDLE,
2805 &all_pinned);
d6d5cfaf 2806 spin_unlock(&busiest->lock);
0a2966b4 2807
969bb4e4 2808 if (unlikely(all_pinned)) {
0a2966b4
CL
2809 cpu_clear(cpu_of(busiest), cpus);
2810 if (!cpus_empty(cpus))
2811 goto redo;
2812 }
d6d5cfaf
NP
2813 }
2814
43010659 2815 if (!ld_moved) {
d15bcfdb 2816 schedstat_inc(sd, lb_failed[CPU_NEWLY_IDLE]);
89c4710e
SS
2817 if (!sd_idle && sd->flags & SD_SHARE_CPUPOWER &&
2818 !test_sd_parent(sd, SD_POWERSAVINGS_BALANCE))
5969fe06
NP
2819 return -1;
2820 } else
16cfb1c0 2821 sd->nr_balance_failed = 0;
1da177e4 2822
43010659 2823 return ld_moved;
16cfb1c0
NP
2824
2825out_balanced:
d15bcfdb 2826 schedstat_inc(sd, lb_balanced[CPU_NEWLY_IDLE]);
48f24c4d 2827 if (!sd_idle && sd->flags & SD_SHARE_CPUPOWER &&
89c4710e 2828 !test_sd_parent(sd, SD_POWERSAVINGS_BALANCE))
5969fe06 2829 return -1;
16cfb1c0 2830 sd->nr_balance_failed = 0;
48f24c4d 2831
16cfb1c0 2832 return 0;
1da177e4
LT
2833}
2834
2835/*
2836 * idle_balance is called by schedule() if this_cpu is about to become
2837 * idle. Attempts to pull tasks from other CPUs.
2838 */
70b97a7f 2839static void idle_balance(int this_cpu, struct rq *this_rq)
1da177e4
LT
2840{
2841 struct sched_domain *sd;
dd41f596
IM
2842 int pulled_task = -1;
2843 unsigned long next_balance = jiffies + HZ;
1da177e4
LT
2844
2845 for_each_domain(this_cpu, sd) {
92c4ca5c
CL
2846 unsigned long interval;
2847
2848 if (!(sd->flags & SD_LOAD_BALANCE))
2849 continue;
2850
2851 if (sd->flags & SD_BALANCE_NEWIDLE)
48f24c4d 2852 /* If we've pulled tasks over stop searching: */
1bd77f2d 2853 pulled_task = load_balance_newidle(this_cpu,
92c4ca5c
CL
2854 this_rq, sd);
2855
2856 interval = msecs_to_jiffies(sd->balance_interval);
2857 if (time_after(next_balance, sd->last_balance + interval))
2858 next_balance = sd->last_balance + interval;
2859 if (pulled_task)
2860 break;
1da177e4 2861 }
dd41f596 2862 if (pulled_task || time_after(jiffies, this_rq->next_balance)) {
1bd77f2d
CL
2863 /*
2864 * We are going idle. next_balance may be set based on
2865 * a busy processor. So reset next_balance.
2866 */
2867 this_rq->next_balance = next_balance;
dd41f596 2868 }
1da177e4
LT
2869}
2870
2871/*
2872 * active_load_balance is run by migration threads. It pushes running tasks
2873 * off the busiest CPU onto idle CPUs. It requires at least 1 task to be
2874 * running on each physical CPU where possible, and avoids physical /
2875 * logical imbalances.
2876 *
2877 * Called with busiest_rq locked.
2878 */
70b97a7f 2879static void active_load_balance(struct rq *busiest_rq, int busiest_cpu)
1da177e4 2880{
39507451 2881 int target_cpu = busiest_rq->push_cpu;
70b97a7f
IM
2882 struct sched_domain *sd;
2883 struct rq *target_rq;
39507451 2884
48f24c4d 2885 /* Is there any task to move? */
39507451 2886 if (busiest_rq->nr_running <= 1)
39507451
NP
2887 return;
2888
2889 target_rq = cpu_rq(target_cpu);
1da177e4
LT
2890
2891 /*
39507451
NP
2892 * This condition is "impossible", if it occurs
2893 * we need to fix it. Originally reported by
2894 * Bjorn Helgaas on a 128-cpu setup.
1da177e4 2895 */
39507451 2896 BUG_ON(busiest_rq == target_rq);
1da177e4 2897
39507451
NP
2898 /* move a task from busiest_rq to target_rq */
2899 double_lock_balance(busiest_rq, target_rq);
2900
2901 /* Search for an sd spanning us and the target CPU. */
c96d145e 2902 for_each_domain(target_cpu, sd) {
39507451 2903 if ((sd->flags & SD_LOAD_BALANCE) &&
48f24c4d 2904 cpu_isset(busiest_cpu, sd->span))
39507451 2905 break;
c96d145e 2906 }
39507451 2907
48f24c4d
IM
2908 if (likely(sd)) {
2909 schedstat_inc(sd, alb_cnt);
39507451 2910
43010659
PW
2911 if (move_one_task(target_rq, target_cpu, busiest_rq,
2912 sd, CPU_IDLE))
48f24c4d
IM
2913 schedstat_inc(sd, alb_pushed);
2914 else
2915 schedstat_inc(sd, alb_failed);
2916 }
39507451 2917 spin_unlock(&target_rq->lock);
1da177e4
LT
2918}
2919
46cb4b7c
SS
2920#ifdef CONFIG_NO_HZ
2921static struct {
2922 atomic_t load_balancer;
2923 cpumask_t cpu_mask;
2924} nohz ____cacheline_aligned = {
2925 .load_balancer = ATOMIC_INIT(-1),
2926 .cpu_mask = CPU_MASK_NONE,
2927};
2928
7835b98b 2929/*
46cb4b7c
SS
2930 * This routine will try to nominate the ilb (idle load balancing)
2931 * owner among the cpus whose ticks are stopped. ilb owner will do the idle
2932 * load balancing on behalf of all those cpus. If all the cpus in the system
2933 * go into this tickless mode, then there will be no ilb owner (as there is
2934 * no need for one) and all the cpus will sleep till the next wakeup event
2935 * arrives...
2936 *
2937 * For the ilb owner, tick is not stopped. And this tick will be used
2938 * for idle load balancing. ilb owner will still be part of
2939 * nohz.cpu_mask..
7835b98b 2940 *
46cb4b7c
SS
2941 * While stopping the tick, this cpu will become the ilb owner if there
2942 * is no other owner. And will be the owner till that cpu becomes busy
2943 * or if all cpus in the system stop their ticks at which point
2944 * there is no need for ilb owner.
2945 *
2946 * When the ilb owner becomes busy, it nominates another owner, during the
2947 * next busy scheduler_tick()
2948 */
2949int select_nohz_load_balancer(int stop_tick)
2950{
2951 int cpu = smp_processor_id();
2952
2953 if (stop_tick) {
2954 cpu_set(cpu, nohz.cpu_mask);
2955 cpu_rq(cpu)->in_nohz_recently = 1;
2956
2957 /*
2958 * If we are going offline and still the leader, give up!
2959 */
2960 if (cpu_is_offline(cpu) &&
2961 atomic_read(&nohz.load_balancer) == cpu) {
2962 if (atomic_cmpxchg(&nohz.load_balancer, cpu, -1) != cpu)
2963 BUG();
2964 return 0;
2965 }
2966
2967 /* time for ilb owner also to sleep */
2968 if (cpus_weight(nohz.cpu_mask) == num_online_cpus()) {
2969 if (atomic_read(&nohz.load_balancer) == cpu)
2970 atomic_set(&nohz.load_balancer, -1);
2971 return 0;
2972 }
2973
2974 if (atomic_read(&nohz.load_balancer) == -1) {
2975 /* make me the ilb owner */
2976 if (atomic_cmpxchg(&nohz.load_balancer, -1, cpu) == -1)
2977 return 1;
2978 } else if (atomic_read(&nohz.load_balancer) == cpu)
2979 return 1;
2980 } else {
2981 if (!cpu_isset(cpu, nohz.cpu_mask))
2982 return 0;
2983
2984 cpu_clear(cpu, nohz.cpu_mask);
2985
2986 if (atomic_read(&nohz.load_balancer) == cpu)
2987 if (atomic_cmpxchg(&nohz.load_balancer, cpu, -1) != cpu)
2988 BUG();
2989 }
2990 return 0;
2991}
2992#endif
2993
2994static DEFINE_SPINLOCK(balancing);
2995
2996/*
7835b98b
CL
2997 * It checks each scheduling domain to see if it is due to be balanced,
2998 * and initiates a balancing operation if so.
2999 *
3000 * Balancing parameters are set up in arch_init_sched_domains.
3001 */
d15bcfdb 3002static inline void rebalance_domains(int cpu, enum cpu_idle_type idle)
7835b98b 3003{
46cb4b7c
SS
3004 int balance = 1;
3005 struct rq *rq = cpu_rq(cpu);
7835b98b
CL
3006 unsigned long interval;
3007 struct sched_domain *sd;
46cb4b7c 3008 /* Earliest time when we have to do rebalance again */
c9819f45 3009 unsigned long next_balance = jiffies + 60*HZ;
1da177e4 3010
46cb4b7c 3011 for_each_domain(cpu, sd) {
1da177e4
LT
3012 if (!(sd->flags & SD_LOAD_BALANCE))
3013 continue;
3014
3015 interval = sd->balance_interval;
d15bcfdb 3016 if (idle != CPU_IDLE)
1da177e4
LT
3017 interval *= sd->busy_factor;
3018
3019 /* scale ms to jiffies */
3020 interval = msecs_to_jiffies(interval);
3021 if (unlikely(!interval))
3022 interval = 1;
dd41f596
IM
3023 if (interval > HZ*NR_CPUS/10)
3024 interval = HZ*NR_CPUS/10;
3025
1da177e4 3026
08c183f3
CL
3027 if (sd->flags & SD_SERIALIZE) {
3028 if (!spin_trylock(&balancing))
3029 goto out;
3030 }
3031
c9819f45 3032 if (time_after_eq(jiffies, sd->last_balance + interval)) {
46cb4b7c 3033 if (load_balance(cpu, rq, sd, idle, &balance)) {
fa3b6ddc
SS
3034 /*
3035 * We've pulled tasks over so either we're no
5969fe06
NP
3036 * longer idle, or one of our SMT siblings is
3037 * not idle.
3038 */
d15bcfdb 3039 idle = CPU_NOT_IDLE;
1da177e4 3040 }
1bd77f2d 3041 sd->last_balance = jiffies;
1da177e4 3042 }
08c183f3
CL
3043 if (sd->flags & SD_SERIALIZE)
3044 spin_unlock(&balancing);
3045out:
c9819f45
CL
3046 if (time_after(next_balance, sd->last_balance + interval))
3047 next_balance = sd->last_balance + interval;
783609c6
SS
3048
3049 /*
3050 * Stop the load balance at this level. There is another
3051 * CPU in our sched group which is doing load balancing more
3052 * actively.
3053 */
3054 if (!balance)
3055 break;
1da177e4 3056 }
46cb4b7c
SS
3057 rq->next_balance = next_balance;
3058}
3059
3060/*
3061 * run_rebalance_domains is triggered when needed from the scheduler tick.
3062 * In CONFIG_NO_HZ case, the idle load balance owner will do the
3063 * rebalancing for all the cpus for whom scheduler ticks are stopped.
3064 */
3065static void run_rebalance_domains(struct softirq_action *h)
3066{
dd41f596
IM
3067 int this_cpu = smp_processor_id();
3068 struct rq *this_rq = cpu_rq(this_cpu);
3069 enum cpu_idle_type idle = this_rq->idle_at_tick ?
3070 CPU_IDLE : CPU_NOT_IDLE;
46cb4b7c 3071
dd41f596 3072 rebalance_domains(this_cpu, idle);
46cb4b7c
SS
3073
3074#ifdef CONFIG_NO_HZ
3075 /*
3076 * If this cpu is the owner for idle load balancing, then do the
3077 * balancing on behalf of the other idle cpus whose ticks are
3078 * stopped.
3079 */
dd41f596
IM
3080 if (this_rq->idle_at_tick &&
3081 atomic_read(&nohz.load_balancer) == this_cpu) {
46cb4b7c
SS
3082 cpumask_t cpus = nohz.cpu_mask;
3083 struct rq *rq;
3084 int balance_cpu;
3085
dd41f596 3086 cpu_clear(this_cpu, cpus);
46cb4b7c
SS
3087 for_each_cpu_mask(balance_cpu, cpus) {
3088 /*
3089 * If this cpu gets work to do, stop the load balancing
3090 * work being done for other cpus. Next load
3091 * balancing owner will pick it up.
3092 */
3093 if (need_resched())
3094 break;
3095
dd41f596 3096 rebalance_domains(balance_cpu, SCHED_IDLE);
46cb4b7c
SS
3097
3098 rq = cpu_rq(balance_cpu);
dd41f596
IM
3099 if (time_after(this_rq->next_balance, rq->next_balance))
3100 this_rq->next_balance = rq->next_balance;
46cb4b7c
SS
3101 }
3102 }
3103#endif
3104}
3105
3106/*
3107 * Trigger the SCHED_SOFTIRQ if it is time to do periodic load balancing.
3108 *
3109 * In case of CONFIG_NO_HZ, this is the place where we nominate a new
3110 * idle load balancing owner or decide to stop the periodic load balancing,
3111 * if the whole system is idle.
3112 */
dd41f596 3113static inline void trigger_load_balance(struct rq *rq, int cpu)
46cb4b7c 3114{
46cb4b7c
SS
3115#ifdef CONFIG_NO_HZ
3116 /*
3117 * If we were in the nohz mode recently and busy at the current
3118 * scheduler tick, then check if we need to nominate new idle
3119 * load balancer.
3120 */
3121 if (rq->in_nohz_recently && !rq->idle_at_tick) {
3122 rq->in_nohz_recently = 0;
3123
3124 if (atomic_read(&nohz.load_balancer) == cpu) {
3125 cpu_clear(cpu, nohz.cpu_mask);
3126 atomic_set(&nohz.load_balancer, -1);
3127 }
3128
3129 if (atomic_read(&nohz.load_balancer) == -1) {
3130 /*
3131 * simple selection for now: Nominate the
3132 * first cpu in the nohz list to be the next
3133 * ilb owner.
3134 *
3135 * TBD: Traverse the sched domains and nominate
3136 * the nearest cpu in the nohz.cpu_mask.
3137 */
3138 int ilb = first_cpu(nohz.cpu_mask);
3139
3140 if (ilb != NR_CPUS)
3141 resched_cpu(ilb);
3142 }
3143 }
3144
3145 /*
3146 * If this cpu is idle and doing idle load balancing for all the
3147 * cpus with ticks stopped, is it time for that to stop?
3148 */
3149 if (rq->idle_at_tick && atomic_read(&nohz.load_balancer) == cpu &&
3150 cpus_weight(nohz.cpu_mask) == num_online_cpus()) {
3151 resched_cpu(cpu);
3152 return;
3153 }
3154
3155 /*
3156 * If this cpu is idle and the idle load balancing is done by
3157 * someone else, then no need raise the SCHED_SOFTIRQ
3158 */
3159 if (rq->idle_at_tick && atomic_read(&nohz.load_balancer) != cpu &&
3160 cpu_isset(cpu, nohz.cpu_mask))
3161 return;
3162#endif
3163 if (time_after_eq(jiffies, rq->next_balance))
3164 raise_softirq(SCHED_SOFTIRQ);
1da177e4 3165}
dd41f596
IM
3166
3167#else /* CONFIG_SMP */
3168
1da177e4
LT
3169/*
3170 * on UP we do not need to balance between CPUs:
3171 */
70b97a7f 3172static inline void idle_balance(int cpu, struct rq *rq)
1da177e4
LT
3173{
3174}
dd41f596
IM
3175
3176/* Avoid "used but not defined" warning on UP */
3177static int balance_tasks(struct rq *this_rq, int this_cpu, struct rq *busiest,
3178 unsigned long max_nr_move, unsigned long max_load_move,
3179 struct sched_domain *sd, enum cpu_idle_type idle,
3180 int *all_pinned, unsigned long *load_moved,
a4ac01c3 3181 int *this_best_prio, struct rq_iterator *iterator)
dd41f596
IM
3182{
3183 *load_moved = 0;
3184
3185 return 0;
3186}
3187
1da177e4
LT
3188#endif
3189
1da177e4
LT
3190DEFINE_PER_CPU(struct kernel_stat, kstat);
3191
3192EXPORT_PER_CPU_SYMBOL(kstat);
3193
3194/*
41b86e9c
IM
3195 * Return p->sum_exec_runtime plus any more ns on the sched_clock
3196 * that have not yet been banked in case the task is currently running.
1da177e4 3197 */
41b86e9c 3198unsigned long long task_sched_runtime(struct task_struct *p)
1da177e4 3199{
1da177e4 3200 unsigned long flags;
41b86e9c
IM
3201 u64 ns, delta_exec;
3202 struct rq *rq;
48f24c4d 3203
41b86e9c
IM
3204 rq = task_rq_lock(p, &flags);
3205 ns = p->se.sum_exec_runtime;
3206 if (rq->curr == p) {
a8e504d2
IM
3207 update_rq_clock(rq);
3208 delta_exec = rq->clock - p->se.exec_start;
41b86e9c
IM
3209 if ((s64)delta_exec > 0)
3210 ns += delta_exec;
3211 }
3212 task_rq_unlock(rq, &flags);
48f24c4d 3213
1da177e4
LT
3214 return ns;
3215}
3216
1da177e4
LT
3217/*
3218 * Account user cpu time to a process.
3219 * @p: the process that the cpu time gets accounted to
3220 * @hardirq_offset: the offset to subtract from hardirq_count()
3221 * @cputime: the cpu time spent in user space since the last update
3222 */
3223void account_user_time(struct task_struct *p, cputime_t cputime)
3224{
3225 struct cpu_usage_stat *cpustat = &kstat_this_cpu.cpustat;
3226 cputime64_t tmp;
3227
3228 p->utime = cputime_add(p->utime, cputime);
3229
3230 /* Add user time to cpustat. */
3231 tmp = cputime_to_cputime64(cputime);
3232 if (TASK_NICE(p) > 0)
3233 cpustat->nice = cputime64_add(cpustat->nice, tmp);
3234 else
3235 cpustat->user = cputime64_add(cpustat->user, tmp);
3236}
3237
3238/*
3239 * Account system cpu time to a process.
3240 * @p: the process that the cpu time gets accounted to
3241 * @hardirq_offset: the offset to subtract from hardirq_count()
3242 * @cputime: the cpu time spent in kernel space since the last update
3243 */
3244void account_system_time(struct task_struct *p, int hardirq_offset,
3245 cputime_t cputime)
3246{
3247 struct cpu_usage_stat *cpustat = &kstat_this_cpu.cpustat;
70b97a7f 3248 struct rq *rq = this_rq();
1da177e4
LT
3249 cputime64_t tmp;
3250
3251 p->stime = cputime_add(p->stime, cputime);
3252
3253 /* Add system time to cpustat. */
3254 tmp = cputime_to_cputime64(cputime);
3255 if (hardirq_count() - hardirq_offset)
3256 cpustat->irq = cputime64_add(cpustat->irq, tmp);
3257 else if (softirq_count())
3258 cpustat->softirq = cputime64_add(cpustat->softirq, tmp);
3259 else if (p != rq->idle)
3260 cpustat->system = cputime64_add(cpustat->system, tmp);
3261 else if (atomic_read(&rq->nr_iowait) > 0)
3262 cpustat->iowait = cputime64_add(cpustat->iowait, tmp);
3263 else
3264 cpustat->idle = cputime64_add(cpustat->idle, tmp);
3265 /* Account for system time used */
3266 acct_update_integrals(p);
1da177e4
LT
3267}
3268
3269/*
3270 * Account for involuntary wait time.
3271 * @p: the process from which the cpu time has been stolen
3272 * @steal: the cpu time spent in involuntary wait
3273 */
3274void account_steal_time(struct task_struct *p, cputime_t steal)
3275{
3276 struct cpu_usage_stat *cpustat = &kstat_this_cpu.cpustat;
3277 cputime64_t tmp = cputime_to_cputime64(steal);
70b97a7f 3278 struct rq *rq = this_rq();
1da177e4
LT
3279
3280 if (p == rq->idle) {
3281 p->stime = cputime_add(p->stime, steal);
3282 if (atomic_read(&rq->nr_iowait) > 0)
3283 cpustat->iowait = cputime64_add(cpustat->iowait, tmp);
3284 else
3285 cpustat->idle = cputime64_add(cpustat->idle, tmp);
3286 } else
3287 cpustat->steal = cputime64_add(cpustat->steal, tmp);
3288}
3289
7835b98b
CL
3290/*
3291 * This function gets called by the timer code, with HZ frequency.
3292 * We call it with interrupts disabled.
3293 *
3294 * It also gets called by the fork code, when changing the parent's
3295 * timeslices.
3296 */
3297void scheduler_tick(void)
3298{
7835b98b
CL
3299 int cpu = smp_processor_id();
3300 struct rq *rq = cpu_rq(cpu);
dd41f596
IM
3301 struct task_struct *curr = rq->curr;
3302
3303 spin_lock(&rq->lock);
f1a438d8 3304 update_cpu_load(rq);
dd41f596
IM
3305 if (curr != rq->idle) /* FIXME: needed? */
3306 curr->sched_class->task_tick(rq, curr);
dd41f596 3307 spin_unlock(&rq->lock);
7835b98b 3308
e418e1c2 3309#ifdef CONFIG_SMP
dd41f596
IM
3310 rq->idle_at_tick = idle_cpu(cpu);
3311 trigger_load_balance(rq, cpu);
e418e1c2 3312#endif
1da177e4
LT
3313}
3314
1da177e4
LT
3315#if defined(CONFIG_PREEMPT) && defined(CONFIG_DEBUG_PREEMPT)
3316
3317void fastcall add_preempt_count(int val)
3318{
3319 /*
3320 * Underflow?
3321 */
9a11b49a
IM
3322 if (DEBUG_LOCKS_WARN_ON((preempt_count() < 0)))
3323 return;
1da177e4
LT
3324 preempt_count() += val;
3325 /*
3326 * Spinlock count overflowing soon?
3327 */
33859f7f
MOS
3328 DEBUG_LOCKS_WARN_ON((preempt_count() & PREEMPT_MASK) >=
3329 PREEMPT_MASK - 10);
1da177e4
LT
3330}
3331EXPORT_SYMBOL(add_preempt_count);
3332
3333void fastcall sub_preempt_count(int val)
3334{
3335 /*
3336 * Underflow?
3337 */
9a11b49a
IM
3338 if (DEBUG_LOCKS_WARN_ON(val > preempt_count()))
3339 return;
1da177e4
LT
3340 /*
3341 * Is the spinlock portion underflowing?
3342 */
9a11b49a
IM
3343 if (DEBUG_LOCKS_WARN_ON((val < PREEMPT_MASK) &&
3344 !(preempt_count() & PREEMPT_MASK)))
3345 return;
3346
1da177e4
LT
3347 preempt_count() -= val;
3348}
3349EXPORT_SYMBOL(sub_preempt_count);
3350
3351#endif
3352
3353/*
dd41f596 3354 * Print scheduling while atomic bug:
1da177e4 3355 */
dd41f596 3356static noinline void __schedule_bug(struct task_struct *prev)
1da177e4 3357{
dd41f596
IM
3358 printk(KERN_ERR "BUG: scheduling while atomic: %s/0x%08x/%d\n",
3359 prev->comm, preempt_count(), prev->pid);
3360 debug_show_held_locks(prev);
3361 if (irqs_disabled())
3362 print_irqtrace_events(prev);
3363 dump_stack();
3364}
1da177e4 3365
dd41f596
IM
3366/*
3367 * Various schedule()-time debugging checks and statistics:
3368 */
3369static inline void schedule_debug(struct task_struct *prev)
3370{
1da177e4
LT
3371 /*
3372 * Test if we are atomic. Since do_exit() needs to call into
3373 * schedule() atomically, we ignore that path for now.
3374 * Otherwise, whine if we are scheduling when we should not be.
3375 */
dd41f596
IM
3376 if (unlikely(in_atomic_preempt_off()) && unlikely(!prev->exit_state))
3377 __schedule_bug(prev);
3378
1da177e4
LT
3379 profile_hit(SCHED_PROFILING, __builtin_return_address(0));
3380
dd41f596
IM
3381 schedstat_inc(this_rq(), sched_cnt);
3382}
3383
3384/*
3385 * Pick up the highest-prio task:
3386 */
3387static inline struct task_struct *
ff95f3df 3388pick_next_task(struct rq *rq, struct task_struct *prev)
dd41f596
IM
3389{
3390 struct sched_class *class;
3391 struct task_struct *p;
1da177e4
LT
3392
3393 /*
dd41f596
IM
3394 * Optimization: we know that if all tasks are in
3395 * the fair class we can call that function directly:
1da177e4 3396 */
dd41f596 3397 if (likely(rq->nr_running == rq->cfs.nr_running)) {
fb8d4724 3398 p = fair_sched_class.pick_next_task(rq);
dd41f596
IM
3399 if (likely(p))
3400 return p;
1da177e4
LT
3401 }
3402
dd41f596
IM
3403 class = sched_class_highest;
3404 for ( ; ; ) {
fb8d4724 3405 p = class->pick_next_task(rq);
dd41f596
IM
3406 if (p)
3407 return p;
3408 /*
3409 * Will never be NULL as the idle class always
3410 * returns a non-NULL p:
3411 */
3412 class = class->next;
3413 }
3414}
1da177e4 3415
dd41f596
IM
3416/*
3417 * schedule() is the main scheduler function.
3418 */
3419asmlinkage void __sched schedule(void)
3420{
3421 struct task_struct *prev, *next;
3422 long *switch_count;
3423 struct rq *rq;
dd41f596
IM
3424 int cpu;
3425
3426need_resched:
3427 preempt_disable();
3428 cpu = smp_processor_id();
3429 rq = cpu_rq(cpu);
3430 rcu_qsctr_inc(cpu);
3431 prev = rq->curr;
3432 switch_count = &prev->nivcsw;
3433
3434 release_kernel_lock(prev);
3435need_resched_nonpreemptible:
3436
3437 schedule_debug(prev);
1da177e4
LT
3438
3439 spin_lock_irq(&rq->lock);
dd41f596 3440 clear_tsk_need_resched(prev);
c1b3da3e 3441 __update_rq_clock(rq);
1da177e4 3442
1da177e4 3443 if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
1da177e4 3444 if (unlikely((prev->state & TASK_INTERRUPTIBLE) &&
dd41f596 3445 unlikely(signal_pending(prev)))) {
1da177e4 3446 prev->state = TASK_RUNNING;
dd41f596 3447 } else {
2e1cb74a 3448 deactivate_task(rq, prev, 1);
1da177e4 3449 }
dd41f596 3450 switch_count = &prev->nvcsw;
1da177e4
LT
3451 }
3452
dd41f596 3453 if (unlikely(!rq->nr_running))
1da177e4 3454 idle_balance(cpu, rq);
1da177e4 3455
31ee529c 3456 prev->sched_class->put_prev_task(rq, prev);
ff95f3df 3457 next = pick_next_task(rq, prev);
1da177e4
LT
3458
3459 sched_info_switch(prev, next);
dd41f596 3460
1da177e4 3461 if (likely(prev != next)) {
1da177e4
LT
3462 rq->nr_switches++;
3463 rq->curr = next;
3464 ++*switch_count;
3465
dd41f596 3466 context_switch(rq, prev, next); /* unlocks the rq */
1da177e4
LT
3467 } else
3468 spin_unlock_irq(&rq->lock);
3469
dd41f596
IM
3470 if (unlikely(reacquire_kernel_lock(current) < 0)) {
3471 cpu = smp_processor_id();
3472 rq = cpu_rq(cpu);
1da177e4 3473 goto need_resched_nonpreemptible;
dd41f596 3474 }
1da177e4
LT
3475 preempt_enable_no_resched();
3476 if (unlikely(test_thread_flag(TIF_NEED_RESCHED)))
3477 goto need_resched;
3478}
1da177e4
LT
3479EXPORT_SYMBOL(schedule);
3480
3481#ifdef CONFIG_PREEMPT
3482/*
2ed6e34f 3483 * this is the entry point to schedule() from in-kernel preemption
1da177e4
LT
3484 * off of preempt_enable. Kernel preemptions off return from interrupt
3485 * occur there and call schedule directly.
3486 */
3487asmlinkage void __sched preempt_schedule(void)
3488{
3489 struct thread_info *ti = current_thread_info();
3490#ifdef CONFIG_PREEMPT_BKL
3491 struct task_struct *task = current;
3492 int saved_lock_depth;
3493#endif
3494 /*
3495 * If there is a non-zero preempt_count or interrupts are disabled,
3496 * we do not want to preempt the current task. Just return..
3497 */
beed33a8 3498 if (likely(ti->preempt_count || irqs_disabled()))
1da177e4
LT
3499 return;
3500
3501need_resched:
3502 add_preempt_count(PREEMPT_ACTIVE);
3503 /*
3504 * We keep the big kernel semaphore locked, but we
3505 * clear ->lock_depth so that schedule() doesnt
3506 * auto-release the semaphore:
3507 */
3508#ifdef CONFIG_PREEMPT_BKL
3509 saved_lock_depth = task->lock_depth;
3510 task->lock_depth = -1;
3511#endif
3512 schedule();
3513#ifdef CONFIG_PREEMPT_BKL
3514 task->lock_depth = saved_lock_depth;
3515#endif
3516 sub_preempt_count(PREEMPT_ACTIVE);
3517
3518 /* we could miss a preemption opportunity between schedule and now */
3519 barrier();
3520 if (unlikely(test_thread_flag(TIF_NEED_RESCHED)))
3521 goto need_resched;
3522}
1da177e4
LT
3523EXPORT_SYMBOL(preempt_schedule);
3524
3525/*
2ed6e34f 3526 * this is the entry point to schedule() from kernel preemption
1da177e4
LT
3527 * off of irq context.
3528 * Note, that this is called and return with irqs disabled. This will
3529 * protect us against recursive calling from irq.
3530 */
3531asmlinkage void __sched preempt_schedule_irq(void)
3532{
3533 struct thread_info *ti = current_thread_info();
3534#ifdef CONFIG_PREEMPT_BKL
3535 struct task_struct *task = current;
3536 int saved_lock_depth;
3537#endif
2ed6e34f 3538 /* Catch callers which need to be fixed */
1da177e4
LT
3539 BUG_ON(ti->preempt_count || !irqs_disabled());
3540
3541need_resched:
3542 add_preempt_count(PREEMPT_ACTIVE);
3543 /*
3544 * We keep the big kernel semaphore locked, but we
3545 * clear ->lock_depth so that schedule() doesnt
3546 * auto-release the semaphore:
3547 */
3548#ifdef CONFIG_PREEMPT_BKL
3549 saved_lock_depth = task->lock_depth;
3550 task->lock_depth = -1;
3551#endif
3552 local_irq_enable();
3553 schedule();
3554 local_irq_disable();
3555#ifdef CONFIG_PREEMPT_BKL
3556 task->lock_depth = saved_lock_depth;
3557#endif
3558 sub_preempt_count(PREEMPT_ACTIVE);
3559
3560 /* we could miss a preemption opportunity between schedule and now */
3561 barrier();
3562 if (unlikely(test_thread_flag(TIF_NEED_RESCHED)))
3563 goto need_resched;
3564}
3565
3566#endif /* CONFIG_PREEMPT */
3567
95cdf3b7
IM
3568int default_wake_function(wait_queue_t *curr, unsigned mode, int sync,
3569 void *key)
1da177e4 3570{
48f24c4d 3571 return try_to_wake_up(curr->private, mode, sync);
1da177e4 3572}
1da177e4
LT
3573EXPORT_SYMBOL(default_wake_function);
3574
3575/*
3576 * The core wakeup function. Non-exclusive wakeups (nr_exclusive == 0) just
3577 * wake everything up. If it's an exclusive wakeup (nr_exclusive == small +ve
3578 * number) then we wake all the non-exclusive tasks and one exclusive task.
3579 *
3580 * There are circumstances in which we can try to wake a task which has already
3581 * started to run but is not in state TASK_RUNNING. try_to_wake_up() returns
3582 * zero in this (rare) case, and we handle it by continuing to scan the queue.
3583 */
3584static void __wake_up_common(wait_queue_head_t *q, unsigned int mode,
3585 int nr_exclusive, int sync, void *key)
3586{
3587 struct list_head *tmp, *next;
3588
3589 list_for_each_safe(tmp, next, &q->task_list) {
48f24c4d
IM
3590 wait_queue_t *curr = list_entry(tmp, wait_queue_t, task_list);
3591 unsigned flags = curr->flags;
3592
1da177e4 3593 if (curr->func(curr, mode, sync, key) &&
48f24c4d 3594 (flags & WQ_FLAG_EXCLUSIVE) && !--nr_exclusive)
1da177e4
LT
3595 break;
3596 }
3597}
3598
3599/**
3600 * __wake_up - wake up threads blocked on a waitqueue.
3601 * @q: the waitqueue
3602 * @mode: which threads
3603 * @nr_exclusive: how many wake-one or wake-many threads to wake up
67be2dd1 3604 * @key: is directly passed to the wakeup function
1da177e4
LT
3605 */
3606void fastcall __wake_up(wait_queue_head_t *q, unsigned int mode,
95cdf3b7 3607 int nr_exclusive, void *key)
1da177e4
LT
3608{
3609 unsigned long flags;
3610
3611 spin_lock_irqsave(&q->lock, flags);
3612 __wake_up_common(q, mode, nr_exclusive, 0, key);
3613 spin_unlock_irqrestore(&q->lock, flags);
3614}
1da177e4
LT
3615EXPORT_SYMBOL(__wake_up);
3616
3617/*
3618 * Same as __wake_up but called with the spinlock in wait_queue_head_t held.
3619 */
3620void fastcall __wake_up_locked(wait_queue_head_t *q, unsigned int mode)
3621{
3622 __wake_up_common(q, mode, 1, 0, NULL);
3623}
3624
3625/**
67be2dd1 3626 * __wake_up_sync - wake up threads blocked on a waitqueue.
1da177e4
LT
3627 * @q: the waitqueue
3628 * @mode: which threads
3629 * @nr_exclusive: how many wake-one or wake-many threads to wake up
3630 *
3631 * The sync wakeup differs that the waker knows that it will schedule
3632 * away soon, so while the target thread will be woken up, it will not
3633 * be migrated to another CPU - ie. the two threads are 'synchronized'
3634 * with each other. This can prevent needless bouncing between CPUs.
3635 *
3636 * On UP it can prevent extra preemption.
3637 */
95cdf3b7
IM
3638void fastcall
3639__wake_up_sync(wait_queue_head_t *q, unsigned int mode, int nr_exclusive)
1da177e4
LT
3640{
3641 unsigned long flags;
3642 int sync = 1;
3643
3644 if (unlikely(!q))
3645 return;
3646
3647 if (unlikely(!nr_exclusive))
3648 sync = 0;
3649
3650 spin_lock_irqsave(&q->lock, flags);
3651 __wake_up_common(q, mode, nr_exclusive, sync, NULL);
3652 spin_unlock_irqrestore(&q->lock, flags);
3653}
3654EXPORT_SYMBOL_GPL(__wake_up_sync); /* For internal use only */
3655
3656void fastcall complete(struct completion *x)
3657{
3658 unsigned long flags;
3659
3660 spin_lock_irqsave(&x->wait.lock, flags);
3661 x->done++;
3662 __wake_up_common(&x->wait, TASK_UNINTERRUPTIBLE | TASK_INTERRUPTIBLE,
3663 1, 0, NULL);
3664 spin_unlock_irqrestore(&x->wait.lock, flags);
3665}
3666EXPORT_SYMBOL(complete);
3667
3668void fastcall complete_all(struct completion *x)
3669{
3670 unsigned long flags;
3671
3672 spin_lock_irqsave(&x->wait.lock, flags);
3673 x->done += UINT_MAX/2;
3674 __wake_up_common(&x->wait, TASK_UNINTERRUPTIBLE | TASK_INTERRUPTIBLE,
3675 0, 0, NULL);
3676 spin_unlock_irqrestore(&x->wait.lock, flags);
3677}
3678EXPORT_SYMBOL(complete_all);
3679
3680void fastcall __sched wait_for_completion(struct completion *x)
3681{
3682 might_sleep();
48f24c4d 3683
1da177e4
LT
3684 spin_lock_irq(&x->wait.lock);
3685 if (!x->done) {
3686 DECLARE_WAITQUEUE(wait, current);
3687
3688 wait.flags |= WQ_FLAG_EXCLUSIVE;
3689 __add_wait_queue_tail(&x->wait, &wait);
3690 do {
3691 __set_current_state(TASK_UNINTERRUPTIBLE);
3692 spin_unlock_irq(&x->wait.lock);
3693 schedule();
3694 spin_lock_irq(&x->wait.lock);
3695 } while (!x->done);
3696 __remove_wait_queue(&x->wait, &wait);
3697 }
3698 x->done--;
3699 spin_unlock_irq(&x->wait.lock);
3700}
3701EXPORT_SYMBOL(wait_for_completion);
3702
3703unsigned long fastcall __sched
3704wait_for_completion_timeout(struct completion *x, unsigned long timeout)
3705{
3706 might_sleep();
3707
3708 spin_lock_irq(&x->wait.lock);
3709 if (!x->done) {
3710 DECLARE_WAITQUEUE(wait, current);
3711
3712 wait.flags |= WQ_FLAG_EXCLUSIVE;
3713 __add_wait_queue_tail(&x->wait, &wait);
3714 do {
3715 __set_current_state(TASK_UNINTERRUPTIBLE);
3716 spin_unlock_irq(&x->wait.lock);
3717 timeout = schedule_timeout(timeout);
3718 spin_lock_irq(&x->wait.lock);
3719 if (!timeout) {
3720 __remove_wait_queue(&x->wait, &wait);
3721 goto out;
3722 }
3723 } while (!x->done);
3724 __remove_wait_queue(&x->wait, &wait);
3725 }
3726 x->done--;
3727out:
3728 spin_unlock_irq(&x->wait.lock);
3729 return timeout;
3730}
3731EXPORT_SYMBOL(wait_for_completion_timeout);
3732
3733int fastcall __sched wait_for_completion_interruptible(struct completion *x)
3734{
3735 int ret = 0;
3736
3737 might_sleep();
3738
3739 spin_lock_irq(&x->wait.lock);
3740 if (!x->done) {
3741 DECLARE_WAITQUEUE(wait, current);
3742
3743 wait.flags |= WQ_FLAG_EXCLUSIVE;
3744 __add_wait_queue_tail(&x->wait, &wait);
3745 do {
3746 if (signal_pending(current)) {
3747 ret = -ERESTARTSYS;
3748 __remove_wait_queue(&x->wait, &wait);
3749 goto out;
3750 }
3751 __set_current_state(TASK_INTERRUPTIBLE);
3752 spin_unlock_irq(&x->wait.lock);
3753 schedule();
3754 spin_lock_irq(&x->wait.lock);
3755 } while (!x->done);
3756 __remove_wait_queue(&x->wait, &wait);
3757 }
3758 x->done--;
3759out:
3760 spin_unlock_irq(&x->wait.lock);
3761
3762 return ret;
3763}
3764EXPORT_SYMBOL(wait_for_completion_interruptible);
3765
3766unsigned long fastcall __sched
3767wait_for_completion_interruptible_timeout(struct completion *x,
3768 unsigned long timeout)
3769{
3770 might_sleep();
3771
3772 spin_lock_irq(&x->wait.lock);
3773 if (!x->done) {
3774 DECLARE_WAITQUEUE(wait, current);
3775
3776 wait.flags |= WQ_FLAG_EXCLUSIVE;
3777 __add_wait_queue_tail(&x->wait, &wait);
3778 do {
3779 if (signal_pending(current)) {
3780 timeout = -ERESTARTSYS;
3781 __remove_wait_queue(&x->wait, &wait);
3782 goto out;
3783 }
3784 __set_current_state(TASK_INTERRUPTIBLE);
3785 spin_unlock_irq(&x->wait.lock);
3786 timeout = schedule_timeout(timeout);
3787 spin_lock_irq(&x->wait.lock);
3788 if (!timeout) {
3789 __remove_wait_queue(&x->wait, &wait);
3790 goto out;
3791 }
3792 } while (!x->done);
3793 __remove_wait_queue(&x->wait, &wait);
3794 }
3795 x->done--;
3796out:
3797 spin_unlock_irq(&x->wait.lock);
3798 return timeout;
3799}
3800EXPORT_SYMBOL(wait_for_completion_interruptible_timeout);
3801
0fec171c
IM
3802static inline void
3803sleep_on_head(wait_queue_head_t *q, wait_queue_t *wait, unsigned long *flags)
3804{
3805 spin_lock_irqsave(&q->lock, *flags);
3806 __add_wait_queue(q, wait);
1da177e4 3807 spin_unlock(&q->lock);
0fec171c 3808}
1da177e4 3809
0fec171c
IM
3810static inline void
3811sleep_on_tail(wait_queue_head_t *q, wait_queue_t *wait, unsigned long *flags)
3812{
3813 spin_lock_irq(&q->lock);
3814 __remove_wait_queue(q, wait);
3815 spin_unlock_irqrestore(&q->lock, *flags);
3816}
1da177e4 3817
0fec171c 3818void __sched interruptible_sleep_on(wait_queue_head_t *q)
1da177e4 3819{
0fec171c
IM
3820 unsigned long flags;
3821 wait_queue_t wait;
3822
3823 init_waitqueue_entry(&wait, current);
1da177e4
LT
3824
3825 current->state = TASK_INTERRUPTIBLE;
3826
0fec171c 3827 sleep_on_head(q, &wait, &flags);
1da177e4 3828 schedule();
0fec171c 3829 sleep_on_tail(q, &wait, &flags);
1da177e4 3830}
1da177e4
LT
3831EXPORT_SYMBOL(interruptible_sleep_on);
3832
0fec171c 3833long __sched
95cdf3b7 3834interruptible_sleep_on_timeout(wait_queue_head_t *q, long timeout)
1da177e4 3835{
0fec171c
IM
3836 unsigned long flags;
3837 wait_queue_t wait;
3838
3839 init_waitqueue_entry(&wait, current);
1da177e4
LT
3840
3841 current->state = TASK_INTERRUPTIBLE;
3842
0fec171c 3843 sleep_on_head(q, &wait, &flags);
1da177e4 3844 timeout = schedule_timeout(timeout);
0fec171c 3845 sleep_on_tail(q, &wait, &flags);
1da177e4
LT
3846
3847 return timeout;
3848}
1da177e4
LT
3849EXPORT_SYMBOL(interruptible_sleep_on_timeout);
3850
0fec171c 3851void __sched sleep_on(wait_queue_head_t *q)
1da177e4 3852{
0fec171c
IM
3853 unsigned long flags;
3854 wait_queue_t wait;
3855
3856 init_waitqueue_entry(&wait, current);
1da177e4
LT
3857
3858 current->state = TASK_UNINTERRUPTIBLE;
3859
0fec171c 3860 sleep_on_head(q, &wait, &flags);
1da177e4 3861 schedule();
0fec171c 3862 sleep_on_tail(q, &wait, &flags);
1da177e4 3863}
1da177e4
LT
3864EXPORT_SYMBOL(sleep_on);
3865
0fec171c 3866long __sched sleep_on_timeout(wait_queue_head_t *q, long timeout)
1da177e4 3867{
0fec171c
IM
3868 unsigned long flags;
3869 wait_queue_t wait;
3870
3871 init_waitqueue_entry(&wait, current);
1da177e4
LT
3872
3873 current->state = TASK_UNINTERRUPTIBLE;
3874
0fec171c 3875 sleep_on_head(q, &wait, &flags);
1da177e4 3876 timeout = schedule_timeout(timeout);
0fec171c 3877 sleep_on_tail(q, &wait, &flags);
1da177e4
LT
3878
3879 return timeout;
3880}
1da177e4
LT
3881EXPORT_SYMBOL(sleep_on_timeout);
3882
b29739f9
IM
3883#ifdef CONFIG_RT_MUTEXES
3884
3885/*
3886 * rt_mutex_setprio - set the current priority of a task
3887 * @p: task
3888 * @prio: prio value (kernel-internal form)
3889 *
3890 * This function changes the 'effective' priority of a task. It does
3891 * not touch ->normal_prio like __setscheduler().
3892 *
3893 * Used by the rt_mutex code to implement priority inheritance logic.
3894 */
36c8b586 3895void rt_mutex_setprio(struct task_struct *p, int prio)
b29739f9
IM
3896{
3897 unsigned long flags;
dd41f596 3898 int oldprio, on_rq;
70b97a7f 3899 struct rq *rq;
b29739f9
IM
3900
3901 BUG_ON(prio < 0 || prio > MAX_PRIO);
3902
3903 rq = task_rq_lock(p, &flags);
a8e504d2 3904 update_rq_clock(rq);
b29739f9 3905
d5f9f942 3906 oldprio = p->prio;
dd41f596
IM
3907 on_rq = p->se.on_rq;
3908 if (on_rq)
69be72c1 3909 dequeue_task(rq, p, 0);
dd41f596
IM
3910
3911 if (rt_prio(prio))
3912 p->sched_class = &rt_sched_class;
3913 else
3914 p->sched_class = &fair_sched_class;
3915
b29739f9
IM
3916 p->prio = prio;
3917
dd41f596 3918 if (on_rq) {
8159f87e 3919 enqueue_task(rq, p, 0);
b29739f9
IM
3920 /*
3921 * Reschedule if we are currently running on this runqueue and
d5f9f942
AM
3922 * our priority decreased, or if we are not currently running on
3923 * this runqueue and our priority is higher than the current's
b29739f9 3924 */
d5f9f942
AM
3925 if (task_running(rq, p)) {
3926 if (p->prio > oldprio)
3927 resched_task(rq->curr);
dd41f596
IM
3928 } else {
3929 check_preempt_curr(rq, p);
3930 }
b29739f9
IM
3931 }
3932 task_rq_unlock(rq, &flags);
3933}
3934
3935#endif
3936
36c8b586 3937void set_user_nice(struct task_struct *p, long nice)
1da177e4 3938{
dd41f596 3939 int old_prio, delta, on_rq;
1da177e4 3940 unsigned long flags;
70b97a7f 3941 struct rq *rq;
1da177e4
LT
3942
3943 if (TASK_NICE(p) == nice || nice < -20 || nice > 19)
3944 return;
3945 /*
3946 * We have to be careful, if called from sys_setpriority(),
3947 * the task might be in the middle of scheduling on another CPU.
3948 */
3949 rq = task_rq_lock(p, &flags);
a8e504d2 3950 update_rq_clock(rq);
1da177e4
LT
3951 /*
3952 * The RT priorities are set via sched_setscheduler(), but we still
3953 * allow the 'normal' nice value to be set - but as expected
3954 * it wont have any effect on scheduling until the task is
dd41f596 3955 * SCHED_FIFO/SCHED_RR:
1da177e4 3956 */
e05606d3 3957 if (task_has_rt_policy(p)) {
1da177e4
LT
3958 p->static_prio = NICE_TO_PRIO(nice);
3959 goto out_unlock;
3960 }
dd41f596
IM
3961 on_rq = p->se.on_rq;
3962 if (on_rq) {
69be72c1 3963 dequeue_task(rq, p, 0);
79b5dddf 3964 dec_load(rq, p);
2dd73a4f 3965 }
1da177e4 3966
1da177e4 3967 p->static_prio = NICE_TO_PRIO(nice);
2dd73a4f 3968 set_load_weight(p);
b29739f9
IM
3969 old_prio = p->prio;
3970 p->prio = effective_prio(p);
3971 delta = p->prio - old_prio;
1da177e4 3972
dd41f596 3973 if (on_rq) {
8159f87e 3974 enqueue_task(rq, p, 0);
29b4b623 3975 inc_load(rq, p);
1da177e4 3976 /*
d5f9f942
AM
3977 * If the task increased its priority or is running and
3978 * lowered its priority, then reschedule its CPU:
1da177e4 3979 */
d5f9f942 3980 if (delta < 0 || (delta > 0 && task_running(rq, p)))
1da177e4
LT
3981 resched_task(rq->curr);
3982 }
3983out_unlock:
3984 task_rq_unlock(rq, &flags);
3985}
1da177e4
LT
3986EXPORT_SYMBOL(set_user_nice);
3987
e43379f1
MM
3988/*
3989 * can_nice - check if a task can reduce its nice value
3990 * @p: task
3991 * @nice: nice value
3992 */
36c8b586 3993int can_nice(const struct task_struct *p, const int nice)
e43379f1 3994{
024f4747
MM
3995 /* convert nice value [19,-20] to rlimit style value [1,40] */
3996 int nice_rlim = 20 - nice;
48f24c4d 3997
e43379f1
MM
3998 return (nice_rlim <= p->signal->rlim[RLIMIT_NICE].rlim_cur ||
3999 capable(CAP_SYS_NICE));
4000}
4001
1da177e4
LT
4002#ifdef __ARCH_WANT_SYS_NICE
4003
4004/*
4005 * sys_nice - change the priority of the current process.
4006 * @increment: priority increment
4007 *
4008 * sys_setpriority is a more generic, but much slower function that
4009 * does similar things.
4010 */
4011asmlinkage long sys_nice(int increment)
4012{
48f24c4d 4013 long nice, retval;
1da177e4
LT
4014
4015 /*
4016 * Setpriority might change our priority at the same moment.
4017 * We don't have to worry. Conceptually one call occurs first
4018 * and we have a single winner.
4019 */
e43379f1
MM
4020 if (increment < -40)
4021 increment = -40;
1da177e4
LT
4022 if (increment > 40)
4023 increment = 40;
4024
4025 nice = PRIO_TO_NICE(current->static_prio) + increment;
4026 if (nice < -20)
4027 nice = -20;
4028 if (nice > 19)
4029 nice = 19;
4030
e43379f1
MM
4031 if (increment < 0 && !can_nice(current, nice))
4032 return -EPERM;
4033
1da177e4
LT
4034 retval = security_task_setnice(current, nice);
4035 if (retval)
4036 return retval;
4037
4038 set_user_nice(current, nice);
4039 return 0;
4040}
4041
4042#endif
4043
4044/**
4045 * task_prio - return the priority value of a given task.
4046 * @p: the task in question.
4047 *
4048 * This is the priority value as seen by users in /proc.
4049 * RT tasks are offset by -200. Normal tasks are centered
4050 * around 0, value goes from -16 to +15.
4051 */
36c8b586 4052int task_prio(const struct task_struct *p)
1da177e4
LT
4053{
4054 return p->prio - MAX_RT_PRIO;
4055}
4056
4057/**
4058 * task_nice - return the nice value of a given task.
4059 * @p: the task in question.
4060 */
36c8b586 4061int task_nice(const struct task_struct *p)
1da177e4
LT
4062{
4063 return TASK_NICE(p);
4064}
1da177e4 4065EXPORT_SYMBOL_GPL(task_nice);
1da177e4
LT
4066
4067/**
4068 * idle_cpu - is a given cpu idle currently?
4069 * @cpu: the processor in question.
4070 */
4071int idle_cpu(int cpu)
4072{
4073 return cpu_curr(cpu) == cpu_rq(cpu)->idle;
4074}
4075
1da177e4
LT
4076/**
4077 * idle_task - return the idle task for a given cpu.
4078 * @cpu: the processor in question.
4079 */
36c8b586 4080struct task_struct *idle_task(int cpu)
1da177e4
LT
4081{
4082 return cpu_rq(cpu)->idle;
4083}
4084
4085/**
4086 * find_process_by_pid - find a process with a matching PID value.
4087 * @pid: the pid in question.
4088 */
36c8b586 4089static inline struct task_struct *find_process_by_pid(pid_t pid)
1da177e4
LT
4090{
4091 return pid ? find_task_by_pid(pid) : current;
4092}
4093
4094/* Actually do priority change: must hold rq lock. */
dd41f596
IM
4095static void
4096__setscheduler(struct rq *rq, struct task_struct *p, int policy, int prio)
1da177e4 4097{
dd41f596 4098 BUG_ON(p->se.on_rq);
48f24c4d 4099
1da177e4 4100 p->policy = policy;
dd41f596
IM
4101 switch (p->policy) {
4102 case SCHED_NORMAL:
4103 case SCHED_BATCH:
4104 case SCHED_IDLE:
4105 p->sched_class = &fair_sched_class;
4106 break;
4107 case SCHED_FIFO:
4108 case SCHED_RR:
4109 p->sched_class = &rt_sched_class;
4110 break;
4111 }
4112
1da177e4 4113 p->rt_priority = prio;
b29739f9
IM
4114 p->normal_prio = normal_prio(p);
4115 /* we are holding p->pi_lock already */
4116 p->prio = rt_mutex_getprio(p);
2dd73a4f 4117 set_load_weight(p);
1da177e4
LT
4118}
4119
4120/**
72fd4a35 4121 * sched_setscheduler - change the scheduling policy and/or RT priority of a thread.
1da177e4
LT
4122 * @p: the task in question.
4123 * @policy: new policy.
4124 * @param: structure containing the new RT priority.
5fe1d75f 4125 *
72fd4a35 4126 * NOTE that the task may be already dead.
1da177e4 4127 */
95cdf3b7
IM
4128int sched_setscheduler(struct task_struct *p, int policy,
4129 struct sched_param *param)
1da177e4 4130{
dd41f596 4131 int retval, oldprio, oldpolicy = -1, on_rq;
1da177e4 4132 unsigned long flags;
70b97a7f 4133 struct rq *rq;
1da177e4 4134
66e5393a
SR
4135 /* may grab non-irq protected spin_locks */
4136 BUG_ON(in_interrupt());
1da177e4
LT
4137recheck:
4138 /* double check policy once rq lock held */
4139 if (policy < 0)
4140 policy = oldpolicy = p->policy;
4141 else if (policy != SCHED_FIFO && policy != SCHED_RR &&
dd41f596
IM
4142 policy != SCHED_NORMAL && policy != SCHED_BATCH &&
4143 policy != SCHED_IDLE)
b0a9499c 4144 return -EINVAL;
1da177e4
LT
4145 /*
4146 * Valid priorities for SCHED_FIFO and SCHED_RR are
dd41f596
IM
4147 * 1..MAX_USER_RT_PRIO-1, valid priority for SCHED_NORMAL,
4148 * SCHED_BATCH and SCHED_IDLE is 0.
1da177e4
LT
4149 */
4150 if (param->sched_priority < 0 ||
95cdf3b7 4151 (p->mm && param->sched_priority > MAX_USER_RT_PRIO-1) ||
d46523ea 4152 (!p->mm && param->sched_priority > MAX_RT_PRIO-1))
1da177e4 4153 return -EINVAL;
e05606d3 4154 if (rt_policy(policy) != (param->sched_priority != 0))
1da177e4
LT
4155 return -EINVAL;
4156
37e4ab3f
OC
4157 /*
4158 * Allow unprivileged RT tasks to decrease priority:
4159 */
4160 if (!capable(CAP_SYS_NICE)) {
e05606d3 4161 if (rt_policy(policy)) {
8dc3e909 4162 unsigned long rlim_rtprio;
8dc3e909
ON
4163
4164 if (!lock_task_sighand(p, &flags))
4165 return -ESRCH;
4166 rlim_rtprio = p->signal->rlim[RLIMIT_RTPRIO].rlim_cur;
4167 unlock_task_sighand(p, &flags);
4168
4169 /* can't set/change the rt policy */
4170 if (policy != p->policy && !rlim_rtprio)
4171 return -EPERM;
4172
4173 /* can't increase priority */
4174 if (param->sched_priority > p->rt_priority &&
4175 param->sched_priority > rlim_rtprio)
4176 return -EPERM;
4177 }
dd41f596
IM
4178 /*
4179 * Like positive nice levels, dont allow tasks to
4180 * move out of SCHED_IDLE either:
4181 */
4182 if (p->policy == SCHED_IDLE && policy != SCHED_IDLE)
4183 return -EPERM;
5fe1d75f 4184
37e4ab3f
OC
4185 /* can't change other user's priorities */
4186 if ((current->euid != p->euid) &&
4187 (current->euid != p->uid))
4188 return -EPERM;
4189 }
1da177e4
LT
4190
4191 retval = security_task_setscheduler(p, policy, param);
4192 if (retval)
4193 return retval;
b29739f9
IM
4194 /*
4195 * make sure no PI-waiters arrive (or leave) while we are
4196 * changing the priority of the task:
4197 */
4198 spin_lock_irqsave(&p->pi_lock, flags);
1da177e4
LT
4199 /*
4200 * To be able to change p->policy safely, the apropriate
4201 * runqueue lock must be held.
4202 */
b29739f9 4203 rq = __task_rq_lock(p);
1da177e4
LT
4204 /* recheck policy now with rq lock held */
4205 if (unlikely(oldpolicy != -1 && oldpolicy != p->policy)) {
4206 policy = oldpolicy = -1;
b29739f9
IM
4207 __task_rq_unlock(rq);
4208 spin_unlock_irqrestore(&p->pi_lock, flags);
1da177e4
LT
4209 goto recheck;
4210 }
dd41f596 4211 on_rq = p->se.on_rq;
a8e504d2
IM
4212 if (on_rq) {
4213 update_rq_clock(rq);
2e1cb74a 4214 deactivate_task(rq, p, 0);
a8e504d2 4215 }
1da177e4 4216 oldprio = p->prio;
dd41f596
IM
4217 __setscheduler(rq, p, policy, param->sched_priority);
4218 if (on_rq) {
4219 activate_task(rq, p, 0);
1da177e4
LT
4220 /*
4221 * Reschedule if we are currently running on this runqueue and
d5f9f942
AM
4222 * our priority decreased, or if we are not currently running on
4223 * this runqueue and our priority is higher than the current's
1da177e4 4224 */
d5f9f942
AM
4225 if (task_running(rq, p)) {
4226 if (p->prio > oldprio)
4227 resched_task(rq->curr);
dd41f596
IM
4228 } else {
4229 check_preempt_curr(rq, p);
4230 }
1da177e4 4231 }
b29739f9
IM
4232 __task_rq_unlock(rq);
4233 spin_unlock_irqrestore(&p->pi_lock, flags);
4234
95e02ca9
TG
4235 rt_mutex_adjust_pi(p);
4236
1da177e4
LT
4237 return 0;
4238}
4239EXPORT_SYMBOL_GPL(sched_setscheduler);
4240
95cdf3b7
IM
4241static int
4242do_sched_setscheduler(pid_t pid, int policy, struct sched_param __user *param)
1da177e4 4243{
1da177e4
LT
4244 struct sched_param lparam;
4245 struct task_struct *p;
36c8b586 4246 int retval;
1da177e4
LT
4247
4248 if (!param || pid < 0)
4249 return -EINVAL;
4250 if (copy_from_user(&lparam, param, sizeof(struct sched_param)))
4251 return -EFAULT;
5fe1d75f
ON
4252
4253 rcu_read_lock();
4254 retval = -ESRCH;
1da177e4 4255 p = find_process_by_pid(pid);
5fe1d75f
ON
4256 if (p != NULL)
4257 retval = sched_setscheduler(p, policy, &lparam);
4258 rcu_read_unlock();
36c8b586 4259
1da177e4
LT
4260 return retval;
4261}
4262
4263/**
4264 * sys_sched_setscheduler - set/change the scheduler policy and RT priority
4265 * @pid: the pid in question.
4266 * @policy: new policy.
4267 * @param: structure containing the new RT priority.
4268 */
4269asmlinkage long sys_sched_setscheduler(pid_t pid, int policy,
4270 struct sched_param __user *param)
4271{
c21761f1
JB
4272 /* negative values for policy are not valid */
4273 if (policy < 0)
4274 return -EINVAL;
4275
1da177e4
LT
4276 return do_sched_setscheduler(pid, policy, param);
4277}
4278
4279/**
4280 * sys_sched_setparam - set/change the RT priority of a thread
4281 * @pid: the pid in question.
4282 * @param: structure containing the new RT priority.
4283 */
4284asmlinkage long sys_sched_setparam(pid_t pid, struct sched_param __user *param)
4285{
4286 return do_sched_setscheduler(pid, -1, param);
4287}
4288
4289/**
4290 * sys_sched_getscheduler - get the policy (scheduling class) of a thread
4291 * @pid: the pid in question.
4292 */
4293asmlinkage long sys_sched_getscheduler(pid_t pid)
4294{
36c8b586 4295 struct task_struct *p;
1da177e4 4296 int retval = -EINVAL;
1da177e4
LT
4297
4298 if (pid < 0)
4299 goto out_nounlock;
4300
4301 retval = -ESRCH;
4302 read_lock(&tasklist_lock);
4303 p = find_process_by_pid(pid);
4304 if (p) {
4305 retval = security_task_getscheduler(p);
4306 if (!retval)
4307 retval = p->policy;
4308 }
4309 read_unlock(&tasklist_lock);
4310
4311out_nounlock:
4312 return retval;
4313}
4314
4315/**
4316 * sys_sched_getscheduler - get the RT priority of a thread
4317 * @pid: the pid in question.
4318 * @param: structure containing the RT priority.
4319 */
4320asmlinkage long sys_sched_getparam(pid_t pid, struct sched_param __user *param)
4321{
4322 struct sched_param lp;
36c8b586 4323 struct task_struct *p;
1da177e4 4324 int retval = -EINVAL;
1da177e4
LT
4325
4326 if (!param || pid < 0)
4327 goto out_nounlock;
4328
4329 read_lock(&tasklist_lock);
4330 p = find_process_by_pid(pid);
4331 retval = -ESRCH;
4332 if (!p)
4333 goto out_unlock;
4334
4335 retval = security_task_getscheduler(p);
4336 if (retval)
4337 goto out_unlock;
4338
4339 lp.sched_priority = p->rt_priority;
4340 read_unlock(&tasklist_lock);
4341
4342 /*
4343 * This one might sleep, we cannot do it with a spinlock held ...
4344 */
4345 retval = copy_to_user(param, &lp, sizeof(*param)) ? -EFAULT : 0;
4346
4347out_nounlock:
4348 return retval;
4349
4350out_unlock:
4351 read_unlock(&tasklist_lock);
4352 return retval;
4353}
4354
4355long sched_setaffinity(pid_t pid, cpumask_t new_mask)
4356{
1da177e4 4357 cpumask_t cpus_allowed;
36c8b586
IM
4358 struct task_struct *p;
4359 int retval;
1da177e4 4360
5be9361c 4361 mutex_lock(&sched_hotcpu_mutex);
1da177e4
LT
4362 read_lock(&tasklist_lock);
4363
4364 p = find_process_by_pid(pid);
4365 if (!p) {
4366 read_unlock(&tasklist_lock);
5be9361c 4367 mutex_unlock(&sched_hotcpu_mutex);
1da177e4
LT
4368 return -ESRCH;
4369 }
4370
4371 /*
4372 * It is not safe to call set_cpus_allowed with the
4373 * tasklist_lock held. We will bump the task_struct's
4374 * usage count and then drop tasklist_lock.
4375 */
4376 get_task_struct(p);
4377 read_unlock(&tasklist_lock);
4378
4379 retval = -EPERM;
4380 if ((current->euid != p->euid) && (current->euid != p->uid) &&
4381 !capable(CAP_SYS_NICE))
4382 goto out_unlock;
4383
e7834f8f
DQ
4384 retval = security_task_setscheduler(p, 0, NULL);
4385 if (retval)
4386 goto out_unlock;
4387
1da177e4
LT
4388 cpus_allowed = cpuset_cpus_allowed(p);
4389 cpus_and(new_mask, new_mask, cpus_allowed);
4390 retval = set_cpus_allowed(p, new_mask);
4391
4392out_unlock:
4393 put_task_struct(p);
5be9361c 4394 mutex_unlock(&sched_hotcpu_mutex);
1da177e4
LT
4395 return retval;
4396}
4397
4398static int get_user_cpu_mask(unsigned long __user *user_mask_ptr, unsigned len,
4399 cpumask_t *new_mask)
4400{
4401 if (len < sizeof(cpumask_t)) {
4402 memset(new_mask, 0, sizeof(cpumask_t));
4403 } else if (len > sizeof(cpumask_t)) {
4404 len = sizeof(cpumask_t);
4405 }
4406 return copy_from_user(new_mask, user_mask_ptr, len) ? -EFAULT : 0;
4407}
4408
4409/**
4410 * sys_sched_setaffinity - set the cpu affinity of a process
4411 * @pid: pid of the process
4412 * @len: length in bytes of the bitmask pointed to by user_mask_ptr
4413 * @user_mask_ptr: user-space pointer to the new cpu mask
4414 */
4415asmlinkage long sys_sched_setaffinity(pid_t pid, unsigned int len,
4416 unsigned long __user *user_mask_ptr)
4417{
4418 cpumask_t new_mask;
4419 int retval;
4420
4421 retval = get_user_cpu_mask(user_mask_ptr, len, &new_mask);
4422 if (retval)
4423 return retval;
4424
4425 return sched_setaffinity(pid, new_mask);
4426}
4427
4428/*
4429 * Represents all cpu's present in the system
4430 * In systems capable of hotplug, this map could dynamically grow
4431 * as new cpu's are detected in the system via any platform specific
4432 * method, such as ACPI for e.g.
4433 */
4434
4cef0c61 4435cpumask_t cpu_present_map __read_mostly;
1da177e4
LT
4436EXPORT_SYMBOL(cpu_present_map);
4437
4438#ifndef CONFIG_SMP
4cef0c61 4439cpumask_t cpu_online_map __read_mostly = CPU_MASK_ALL;
e16b38f7
GB
4440EXPORT_SYMBOL(cpu_online_map);
4441
4cef0c61 4442cpumask_t cpu_possible_map __read_mostly = CPU_MASK_ALL;
e16b38f7 4443EXPORT_SYMBOL(cpu_possible_map);
1da177e4
LT
4444#endif
4445
4446long sched_getaffinity(pid_t pid, cpumask_t *mask)
4447{
36c8b586 4448 struct task_struct *p;
1da177e4 4449 int retval;
1da177e4 4450
5be9361c 4451 mutex_lock(&sched_hotcpu_mutex);
1da177e4
LT
4452 read_lock(&tasklist_lock);
4453
4454 retval = -ESRCH;
4455 p = find_process_by_pid(pid);
4456 if (!p)
4457 goto out_unlock;
4458
e7834f8f
DQ
4459 retval = security_task_getscheduler(p);
4460 if (retval)
4461 goto out_unlock;
4462
2f7016d9 4463 cpus_and(*mask, p->cpus_allowed, cpu_online_map);
1da177e4
LT
4464
4465out_unlock:
4466 read_unlock(&tasklist_lock);
5be9361c 4467 mutex_unlock(&sched_hotcpu_mutex);
1da177e4 4468
9531b62f 4469 return retval;
1da177e4
LT
4470}
4471
4472/**
4473 * sys_sched_getaffinity - get the cpu affinity of a process
4474 * @pid: pid of the process
4475 * @len: length in bytes of the bitmask pointed to by user_mask_ptr
4476 * @user_mask_ptr: user-space pointer to hold the current cpu mask
4477 */
4478asmlinkage long sys_sched_getaffinity(pid_t pid, unsigned int len,
4479 unsigned long __user *user_mask_ptr)
4480{
4481 int ret;
4482 cpumask_t mask;
4483
4484 if (len < sizeof(cpumask_t))
4485 return -EINVAL;
4486
4487 ret = sched_getaffinity(pid, &mask);
4488 if (ret < 0)
4489 return ret;
4490
4491 if (copy_to_user(user_mask_ptr, &mask, sizeof(cpumask_t)))
4492 return -EFAULT;
4493
4494 return sizeof(cpumask_t);
4495}
4496
4497/**
4498 * sys_sched_yield - yield the current processor to other threads.
4499 *
dd41f596
IM
4500 * This function yields the current CPU to other tasks. If there are no
4501 * other threads running on this CPU then this function will return.
1da177e4
LT
4502 */
4503asmlinkage long sys_sched_yield(void)
4504{
70b97a7f 4505 struct rq *rq = this_rq_lock();
1da177e4
LT
4506
4507 schedstat_inc(rq, yld_cnt);
dd41f596 4508 if (unlikely(rq->nr_running == 1))
1da177e4 4509 schedstat_inc(rq, yld_act_empty);
dd41f596
IM
4510 else
4511 current->sched_class->yield_task(rq, current);
1da177e4
LT
4512
4513 /*
4514 * Since we are going to call schedule() anyway, there's
4515 * no need to preempt or enable interrupts:
4516 */
4517 __release(rq->lock);
8a25d5de 4518 spin_release(&rq->lock.dep_map, 1, _THIS_IP_);
1da177e4
LT
4519 _raw_spin_unlock(&rq->lock);
4520 preempt_enable_no_resched();
4521
4522 schedule();
4523
4524 return 0;
4525}
4526
e7b38404 4527static void __cond_resched(void)
1da177e4 4528{
8e0a43d8
IM
4529#ifdef CONFIG_DEBUG_SPINLOCK_SLEEP
4530 __might_sleep(__FILE__, __LINE__);
4531#endif
5bbcfd90
IM
4532 /*
4533 * The BKS might be reacquired before we have dropped
4534 * PREEMPT_ACTIVE, which could trigger a second
4535 * cond_resched() call.
4536 */
1da177e4
LT
4537 do {
4538 add_preempt_count(PREEMPT_ACTIVE);
4539 schedule();
4540 sub_preempt_count(PREEMPT_ACTIVE);
4541 } while (need_resched());
4542}
4543
4544int __sched cond_resched(void)
4545{
9414232f
IM
4546 if (need_resched() && !(preempt_count() & PREEMPT_ACTIVE) &&
4547 system_state == SYSTEM_RUNNING) {
1da177e4
LT
4548 __cond_resched();
4549 return 1;
4550 }
4551 return 0;
4552}
1da177e4
LT
4553EXPORT_SYMBOL(cond_resched);
4554
4555/*
4556 * cond_resched_lock() - if a reschedule is pending, drop the given lock,
4557 * call schedule, and on return reacquire the lock.
4558 *
4559 * This works OK both with and without CONFIG_PREEMPT. We do strange low-level
4560 * operations here to prevent schedule() from being called twice (once via
4561 * spin_unlock(), once by hand).
4562 */
95cdf3b7 4563int cond_resched_lock(spinlock_t *lock)
1da177e4 4564{
6df3cecb
JK
4565 int ret = 0;
4566
1da177e4
LT
4567 if (need_lockbreak(lock)) {
4568 spin_unlock(lock);
4569 cpu_relax();
6df3cecb 4570 ret = 1;
1da177e4
LT
4571 spin_lock(lock);
4572 }
9414232f 4573 if (need_resched() && system_state == SYSTEM_RUNNING) {
8a25d5de 4574 spin_release(&lock->dep_map, 1, _THIS_IP_);
1da177e4
LT
4575 _raw_spin_unlock(lock);
4576 preempt_enable_no_resched();
4577 __cond_resched();
6df3cecb 4578 ret = 1;
1da177e4 4579 spin_lock(lock);
1da177e4 4580 }
6df3cecb 4581 return ret;
1da177e4 4582}
1da177e4
LT
4583EXPORT_SYMBOL(cond_resched_lock);
4584
4585int __sched cond_resched_softirq(void)
4586{
4587 BUG_ON(!in_softirq());
4588
9414232f 4589 if (need_resched() && system_state == SYSTEM_RUNNING) {
98d82567 4590 local_bh_enable();
1da177e4
LT
4591 __cond_resched();
4592 local_bh_disable();
4593 return 1;
4594 }
4595 return 0;
4596}
1da177e4
LT
4597EXPORT_SYMBOL(cond_resched_softirq);
4598
1da177e4
LT
4599/**
4600 * yield - yield the current processor to other threads.
4601 *
72fd4a35 4602 * This is a shortcut for kernel-space yielding - it marks the
1da177e4
LT
4603 * thread runnable and calls sys_sched_yield().
4604 */
4605void __sched yield(void)
4606{
4607 set_current_state(TASK_RUNNING);
4608 sys_sched_yield();
4609}
1da177e4
LT
4610EXPORT_SYMBOL(yield);
4611
4612/*
4613 * This task is about to go to sleep on IO. Increment rq->nr_iowait so
4614 * that process accounting knows that this is a task in IO wait state.
4615 *
4616 * But don't do that if it is a deliberate, throttling IO wait (this task
4617 * has set its backing_dev_info: the queue against which it should throttle)
4618 */
4619void __sched io_schedule(void)
4620{
70b97a7f 4621 struct rq *rq = &__raw_get_cpu_var(runqueues);
1da177e4 4622
0ff92245 4623 delayacct_blkio_start();
1da177e4
LT
4624 atomic_inc(&rq->nr_iowait);
4625 schedule();
4626 atomic_dec(&rq->nr_iowait);
0ff92245 4627 delayacct_blkio_end();
1da177e4 4628}
1da177e4
LT
4629EXPORT_SYMBOL(io_schedule);
4630
4631long __sched io_schedule_timeout(long timeout)
4632{
70b97a7f 4633 struct rq *rq = &__raw_get_cpu_var(runqueues);
1da177e4
LT
4634 long ret;
4635
0ff92245 4636 delayacct_blkio_start();
1da177e4
LT
4637 atomic_inc(&rq->nr_iowait);
4638 ret = schedule_timeout(timeout);
4639 atomic_dec(&rq->nr_iowait);
0ff92245 4640 delayacct_blkio_end();
1da177e4
LT
4641 return ret;
4642}
4643
4644/**
4645 * sys_sched_get_priority_max - return maximum RT priority.
4646 * @policy: scheduling class.
4647 *
4648 * this syscall returns the maximum rt_priority that can be used
4649 * by a given scheduling class.
4650 */
4651asmlinkage long sys_sched_get_priority_max(int policy)
4652{
4653 int ret = -EINVAL;
4654
4655 switch (policy) {
4656 case SCHED_FIFO:
4657 case SCHED_RR:
4658 ret = MAX_USER_RT_PRIO-1;
4659 break;
4660 case SCHED_NORMAL:
b0a9499c 4661 case SCHED_BATCH:
dd41f596 4662 case SCHED_IDLE:
1da177e4
LT
4663 ret = 0;
4664 break;
4665 }
4666 return ret;
4667}
4668
4669/**
4670 * sys_sched_get_priority_min - return minimum RT priority.
4671 * @policy: scheduling class.
4672 *
4673 * this syscall returns the minimum rt_priority that can be used
4674 * by a given scheduling class.
4675 */
4676asmlinkage long sys_sched_get_priority_min(int policy)
4677{
4678 int ret = -EINVAL;
4679
4680 switch (policy) {
4681 case SCHED_FIFO:
4682 case SCHED_RR:
4683 ret = 1;
4684 break;
4685 case SCHED_NORMAL:
b0a9499c 4686 case SCHED_BATCH:
dd41f596 4687 case SCHED_IDLE:
1da177e4
LT
4688 ret = 0;
4689 }
4690 return ret;
4691}
4692
4693/**
4694 * sys_sched_rr_get_interval - return the default timeslice of a process.
4695 * @pid: pid of the process.
4696 * @interval: userspace pointer to the timeslice value.
4697 *
4698 * this syscall writes the default timeslice value of a given process
4699 * into the user-space timespec buffer. A value of '0' means infinity.
4700 */
4701asmlinkage
4702long sys_sched_rr_get_interval(pid_t pid, struct timespec __user *interval)
4703{
36c8b586 4704 struct task_struct *p;
1da177e4
LT
4705 int retval = -EINVAL;
4706 struct timespec t;
1da177e4
LT
4707
4708 if (pid < 0)
4709 goto out_nounlock;
4710
4711 retval = -ESRCH;
4712 read_lock(&tasklist_lock);
4713 p = find_process_by_pid(pid);
4714 if (!p)
4715 goto out_unlock;
4716
4717 retval = security_task_getscheduler(p);
4718 if (retval)
4719 goto out_unlock;
4720
b78709cf 4721 jiffies_to_timespec(p->policy == SCHED_FIFO ?
dd41f596 4722 0 : static_prio_timeslice(p->static_prio), &t);
1da177e4
LT
4723 read_unlock(&tasklist_lock);
4724 retval = copy_to_user(interval, &t, sizeof(t)) ? -EFAULT : 0;
4725out_nounlock:
4726 return retval;
4727out_unlock:
4728 read_unlock(&tasklist_lock);
4729 return retval;
4730}
4731
2ed6e34f 4732static const char stat_nam[] = "RSDTtZX";
36c8b586
IM
4733
4734static void show_task(struct task_struct *p)
1da177e4 4735{
1da177e4 4736 unsigned long free = 0;
36c8b586 4737 unsigned state;
1da177e4 4738
1da177e4 4739 state = p->state ? __ffs(p->state) + 1 : 0;
2ed6e34f
AM
4740 printk("%-13.13s %c", p->comm,
4741 state < sizeof(stat_nam) - 1 ? stat_nam[state] : '?');
4bd77321 4742#if BITS_PER_LONG == 32
1da177e4 4743 if (state == TASK_RUNNING)
4bd77321 4744 printk(" running ");
1da177e4 4745 else
4bd77321 4746 printk(" %08lx ", thread_saved_pc(p));
1da177e4
LT
4747#else
4748 if (state == TASK_RUNNING)
4bd77321 4749 printk(" running task ");
1da177e4
LT
4750 else
4751 printk(" %016lx ", thread_saved_pc(p));
4752#endif
4753#ifdef CONFIG_DEBUG_STACK_USAGE
4754 {
10ebffde 4755 unsigned long *n = end_of_stack(p);
1da177e4
LT
4756 while (!*n)
4757 n++;
10ebffde 4758 free = (unsigned long)n - (unsigned long)end_of_stack(p);
1da177e4
LT
4759 }
4760#endif
4bd77321 4761 printk("%5lu %5d %6d\n", free, p->pid, p->parent->pid);
1da177e4
LT
4762
4763 if (state != TASK_RUNNING)
4764 show_stack(p, NULL);
4765}
4766
e59e2ae2 4767void show_state_filter(unsigned long state_filter)
1da177e4 4768{
36c8b586 4769 struct task_struct *g, *p;
1da177e4 4770
4bd77321
IM
4771#if BITS_PER_LONG == 32
4772 printk(KERN_INFO
4773 " task PC stack pid father\n");
1da177e4 4774#else
4bd77321
IM
4775 printk(KERN_INFO
4776 " task PC stack pid father\n");
1da177e4
LT
4777#endif
4778 read_lock(&tasklist_lock);
4779 do_each_thread(g, p) {
4780 /*
4781 * reset the NMI-timeout, listing all files on a slow
4782 * console might take alot of time:
4783 */
4784 touch_nmi_watchdog();
39bc89fd 4785 if (!state_filter || (p->state & state_filter))
e59e2ae2 4786 show_task(p);
1da177e4
LT
4787 } while_each_thread(g, p);
4788
04c9167f
JF
4789 touch_all_softlockup_watchdogs();
4790
dd41f596
IM
4791#ifdef CONFIG_SCHED_DEBUG
4792 sysrq_sched_debug_show();
4793#endif
1da177e4 4794 read_unlock(&tasklist_lock);
e59e2ae2
IM
4795 /*
4796 * Only show locks if all tasks are dumped:
4797 */
4798 if (state_filter == -1)
4799 debug_show_all_locks();
1da177e4
LT
4800}
4801
1df21055
IM
4802void __cpuinit init_idle_bootup_task(struct task_struct *idle)
4803{
dd41f596 4804 idle->sched_class = &idle_sched_class;
1df21055
IM
4805}
4806
f340c0d1
IM
4807/**
4808 * init_idle - set up an idle thread for a given CPU
4809 * @idle: task in question
4810 * @cpu: cpu the idle task belongs to
4811 *
4812 * NOTE: this function does not set the idle thread's NEED_RESCHED
4813 * flag, to make booting more robust.
4814 */
5c1e1767 4815void __cpuinit init_idle(struct task_struct *idle, int cpu)
1da177e4 4816{
70b97a7f 4817 struct rq *rq = cpu_rq(cpu);
1da177e4
LT
4818 unsigned long flags;
4819
dd41f596
IM
4820 __sched_fork(idle);
4821 idle->se.exec_start = sched_clock();
4822
b29739f9 4823 idle->prio = idle->normal_prio = MAX_PRIO;
1da177e4 4824 idle->cpus_allowed = cpumask_of_cpu(cpu);
dd41f596 4825 __set_task_cpu(idle, cpu);
1da177e4
LT
4826
4827 spin_lock_irqsave(&rq->lock, flags);
4828 rq->curr = rq->idle = idle;
4866cde0
NP
4829#if defined(CONFIG_SMP) && defined(__ARCH_WANT_UNLOCKED_CTXSW)
4830 idle->oncpu = 1;
4831#endif
1da177e4
LT
4832 spin_unlock_irqrestore(&rq->lock, flags);
4833
4834 /* Set the preempt count _outside_ the spinlocks! */
4835#if defined(CONFIG_PREEMPT) && !defined(CONFIG_PREEMPT_BKL)
a1261f54 4836 task_thread_info(idle)->preempt_count = (idle->lock_depth >= 0);
1da177e4 4837#else
a1261f54 4838 task_thread_info(idle)->preempt_count = 0;
1da177e4 4839#endif
dd41f596
IM
4840 /*
4841 * The idle tasks have their own, simple scheduling class:
4842 */
4843 idle->sched_class = &idle_sched_class;
1da177e4
LT
4844}
4845
4846/*
4847 * In a system that switches off the HZ timer nohz_cpu_mask
4848 * indicates which cpus entered this state. This is used
4849 * in the rcu update to wait only for active cpus. For system
4850 * which do not switch off the HZ timer nohz_cpu_mask should
4851 * always be CPU_MASK_NONE.
4852 */
4853cpumask_t nohz_cpu_mask = CPU_MASK_NONE;
4854
dd41f596
IM
4855/*
4856 * Increase the granularity value when there are more CPUs,
4857 * because with more CPUs the 'effective latency' as visible
4858 * to users decreases. But the relationship is not linear,
4859 * so pick a second-best guess by going with the log2 of the
4860 * number of CPUs.
4861 *
4862 * This idea comes from the SD scheduler of Con Kolivas:
4863 */
4864static inline void sched_init_granularity(void)
4865{
4866 unsigned int factor = 1 + ilog2(num_online_cpus());
a5968df8 4867 const unsigned long gran_limit = 100000000;
dd41f596
IM
4868
4869 sysctl_sched_granularity *= factor;
4870 if (sysctl_sched_granularity > gran_limit)
4871 sysctl_sched_granularity = gran_limit;
4872
4873 sysctl_sched_runtime_limit = sysctl_sched_granularity * 4;
4874 sysctl_sched_wakeup_granularity = sysctl_sched_granularity / 2;
4875}
4876
1da177e4
LT
4877#ifdef CONFIG_SMP
4878/*
4879 * This is how migration works:
4880 *
70b97a7f 4881 * 1) we queue a struct migration_req structure in the source CPU's
1da177e4
LT
4882 * runqueue and wake up that CPU's migration thread.
4883 * 2) we down() the locked semaphore => thread blocks.
4884 * 3) migration thread wakes up (implicitly it forces the migrated
4885 * thread off the CPU)
4886 * 4) it gets the migration request and checks whether the migrated
4887 * task is still in the wrong runqueue.
4888 * 5) if it's in the wrong runqueue then the migration thread removes
4889 * it and puts it into the right queue.
4890 * 6) migration thread up()s the semaphore.
4891 * 7) we wake up and the migration is done.
4892 */
4893
4894/*
4895 * Change a given task's CPU affinity. Migrate the thread to a
4896 * proper CPU and schedule it away if the CPU it's executing on
4897 * is removed from the allowed bitmask.
4898 *
4899 * NOTE: the caller must have a valid reference to the task, the
4900 * task must not exit() & deallocate itself prematurely. The
4901 * call is not atomic; no spinlocks may be held.
4902 */
36c8b586 4903int set_cpus_allowed(struct task_struct *p, cpumask_t new_mask)
1da177e4 4904{
70b97a7f 4905 struct migration_req req;
1da177e4 4906 unsigned long flags;
70b97a7f 4907 struct rq *rq;
48f24c4d 4908 int ret = 0;
1da177e4
LT
4909
4910 rq = task_rq_lock(p, &flags);
4911 if (!cpus_intersects(new_mask, cpu_online_map)) {
4912 ret = -EINVAL;
4913 goto out;
4914 }
4915
4916 p->cpus_allowed = new_mask;
4917 /* Can the task run on the task's current CPU? If so, we're done */
4918 if (cpu_isset(task_cpu(p), new_mask))
4919 goto out;
4920
4921 if (migrate_task(p, any_online_cpu(new_mask), &req)) {
4922 /* Need help from migration thread: drop lock and wait. */
4923 task_rq_unlock(rq, &flags);
4924 wake_up_process(rq->migration_thread);
4925 wait_for_completion(&req.done);
4926 tlb_migrate_finish(p->mm);
4927 return 0;
4928 }
4929out:
4930 task_rq_unlock(rq, &flags);
48f24c4d 4931
1da177e4
LT
4932 return ret;
4933}
1da177e4
LT
4934EXPORT_SYMBOL_GPL(set_cpus_allowed);
4935
4936/*
4937 * Move (not current) task off this cpu, onto dest cpu. We're doing
4938 * this because either it can't run here any more (set_cpus_allowed()
4939 * away from this CPU, or CPU going down), or because we're
4940 * attempting to rebalance this task on exec (sched_exec).
4941 *
4942 * So we race with normal scheduler movements, but that's OK, as long
4943 * as the task is no longer on this CPU.
efc30814
KK
4944 *
4945 * Returns non-zero if task was successfully migrated.
1da177e4 4946 */
efc30814 4947static int __migrate_task(struct task_struct *p, int src_cpu, int dest_cpu)
1da177e4 4948{
70b97a7f 4949 struct rq *rq_dest, *rq_src;
dd41f596 4950 int ret = 0, on_rq;
1da177e4
LT
4951
4952 if (unlikely(cpu_is_offline(dest_cpu)))
efc30814 4953 return ret;
1da177e4
LT
4954
4955 rq_src = cpu_rq(src_cpu);
4956 rq_dest = cpu_rq(dest_cpu);
4957
4958 double_rq_lock(rq_src, rq_dest);
4959 /* Already moved. */
4960 if (task_cpu(p) != src_cpu)
4961 goto out;
4962 /* Affinity changed (again). */
4963 if (!cpu_isset(dest_cpu, p->cpus_allowed))
4964 goto out;
4965
dd41f596 4966 on_rq = p->se.on_rq;
a8e504d2
IM
4967 if (on_rq) {
4968 update_rq_clock(rq_src);
2e1cb74a 4969 deactivate_task(rq_src, p, 0);
a8e504d2 4970 }
1da177e4 4971 set_task_cpu(p, dest_cpu);
dd41f596
IM
4972 if (on_rq) {
4973 activate_task(rq_dest, p, 0);
4974 check_preempt_curr(rq_dest, p);
1da177e4 4975 }
efc30814 4976 ret = 1;
1da177e4
LT
4977out:
4978 double_rq_unlock(rq_src, rq_dest);
efc30814 4979 return ret;
1da177e4
LT
4980}
4981
4982/*
4983 * migration_thread - this is a highprio system thread that performs
4984 * thread migration by bumping thread off CPU then 'pushing' onto
4985 * another runqueue.
4986 */
95cdf3b7 4987static int migration_thread(void *data)
1da177e4 4988{
1da177e4 4989 int cpu = (long)data;
70b97a7f 4990 struct rq *rq;
1da177e4
LT
4991
4992 rq = cpu_rq(cpu);
4993 BUG_ON(rq->migration_thread != current);
4994
4995 set_current_state(TASK_INTERRUPTIBLE);
4996 while (!kthread_should_stop()) {
70b97a7f 4997 struct migration_req *req;
1da177e4 4998 struct list_head *head;
1da177e4 4999
1da177e4
LT
5000 spin_lock_irq(&rq->lock);
5001
5002 if (cpu_is_offline(cpu)) {
5003 spin_unlock_irq(&rq->lock);
5004 goto wait_to_die;
5005 }
5006
5007 if (rq->active_balance) {
5008 active_load_balance(rq, cpu);
5009 rq->active_balance = 0;
5010 }
5011
5012 head = &rq->migration_queue;
5013
5014 if (list_empty(head)) {
5015 spin_unlock_irq(&rq->lock);
5016 schedule();
5017 set_current_state(TASK_INTERRUPTIBLE);
5018 continue;
5019 }
70b97a7f 5020 req = list_entry(head->next, struct migration_req, list);
1da177e4
LT
5021 list_del_init(head->next);
5022
674311d5
NP
5023 spin_unlock(&rq->lock);
5024 __migrate_task(req->task, cpu, req->dest_cpu);
5025 local_irq_enable();
1da177e4
LT
5026
5027 complete(&req->done);
5028 }
5029 __set_current_state(TASK_RUNNING);
5030 return 0;
5031
5032wait_to_die:
5033 /* Wait for kthread_stop */
5034 set_current_state(TASK_INTERRUPTIBLE);
5035 while (!kthread_should_stop()) {
5036 schedule();
5037 set_current_state(TASK_INTERRUPTIBLE);
5038 }
5039 __set_current_state(TASK_RUNNING);
5040 return 0;
5041}
5042
5043#ifdef CONFIG_HOTPLUG_CPU
054b9108
KK
5044/*
5045 * Figure out where task on dead CPU should go, use force if neccessary.
5046 * NOTE: interrupts should be disabled by the caller
5047 */
48f24c4d 5048static void move_task_off_dead_cpu(int dead_cpu, struct task_struct *p)
1da177e4 5049{
efc30814 5050 unsigned long flags;
1da177e4 5051 cpumask_t mask;
70b97a7f
IM
5052 struct rq *rq;
5053 int dest_cpu;
1da177e4 5054
efc30814 5055restart:
1da177e4
LT
5056 /* On same node? */
5057 mask = node_to_cpumask(cpu_to_node(dead_cpu));
48f24c4d 5058 cpus_and(mask, mask, p->cpus_allowed);
1da177e4
LT
5059 dest_cpu = any_online_cpu(mask);
5060
5061 /* On any allowed CPU? */
5062 if (dest_cpu == NR_CPUS)
48f24c4d 5063 dest_cpu = any_online_cpu(p->cpus_allowed);
1da177e4
LT
5064
5065 /* No more Mr. Nice Guy. */
5066 if (dest_cpu == NR_CPUS) {
48f24c4d
IM
5067 rq = task_rq_lock(p, &flags);
5068 cpus_setall(p->cpus_allowed);
5069 dest_cpu = any_online_cpu(p->cpus_allowed);
efc30814 5070 task_rq_unlock(rq, &flags);
1da177e4
LT
5071
5072 /*
5073 * Don't tell them about moving exiting tasks or
5074 * kernel threads (both mm NULL), since they never
5075 * leave kernel.
5076 */
48f24c4d 5077 if (p->mm && printk_ratelimit())
1da177e4
LT
5078 printk(KERN_INFO "process %d (%s) no "
5079 "longer affine to cpu%d\n",
48f24c4d 5080 p->pid, p->comm, dead_cpu);
1da177e4 5081 }
48f24c4d 5082 if (!__migrate_task(p, dead_cpu, dest_cpu))
efc30814 5083 goto restart;
1da177e4
LT
5084}
5085
5086/*
5087 * While a dead CPU has no uninterruptible tasks queued at this point,
5088 * it might still have a nonzero ->nr_uninterruptible counter, because
5089 * for performance reasons the counter is not stricly tracking tasks to
5090 * their home CPUs. So we just add the counter to another CPU's counter,
5091 * to keep the global sum constant after CPU-down:
5092 */
70b97a7f 5093static void migrate_nr_uninterruptible(struct rq *rq_src)
1da177e4 5094{
70b97a7f 5095 struct rq *rq_dest = cpu_rq(any_online_cpu(CPU_MASK_ALL));
1da177e4
LT
5096 unsigned long flags;
5097
5098 local_irq_save(flags);
5099 double_rq_lock(rq_src, rq_dest);
5100 rq_dest->nr_uninterruptible += rq_src->nr_uninterruptible;
5101 rq_src->nr_uninterruptible = 0;
5102 double_rq_unlock(rq_src, rq_dest);
5103 local_irq_restore(flags);
5104}
5105
5106/* Run through task list and migrate tasks from the dead cpu. */
5107static void migrate_live_tasks(int src_cpu)
5108{
48f24c4d 5109 struct task_struct *p, *t;
1da177e4
LT
5110
5111 write_lock_irq(&tasklist_lock);
5112
48f24c4d
IM
5113 do_each_thread(t, p) {
5114 if (p == current)
1da177e4
LT
5115 continue;
5116
48f24c4d
IM
5117 if (task_cpu(p) == src_cpu)
5118 move_task_off_dead_cpu(src_cpu, p);
5119 } while_each_thread(t, p);
1da177e4
LT
5120
5121 write_unlock_irq(&tasklist_lock);
5122}
5123
dd41f596
IM
5124/*
5125 * Schedules idle task to be the next runnable task on current CPU.
1da177e4 5126 * It does so by boosting its priority to highest possible and adding it to
48f24c4d 5127 * the _front_ of the runqueue. Used by CPU offline code.
1da177e4
LT
5128 */
5129void sched_idle_next(void)
5130{
48f24c4d 5131 int this_cpu = smp_processor_id();
70b97a7f 5132 struct rq *rq = cpu_rq(this_cpu);
1da177e4
LT
5133 struct task_struct *p = rq->idle;
5134 unsigned long flags;
5135
5136 /* cpu has to be offline */
48f24c4d 5137 BUG_ON(cpu_online(this_cpu));
1da177e4 5138
48f24c4d
IM
5139 /*
5140 * Strictly not necessary since rest of the CPUs are stopped by now
5141 * and interrupts disabled on the current cpu.
1da177e4
LT
5142 */
5143 spin_lock_irqsave(&rq->lock, flags);
5144
dd41f596 5145 __setscheduler(rq, p, SCHED_FIFO, MAX_RT_PRIO-1);
48f24c4d
IM
5146
5147 /* Add idle task to the _front_ of its priority queue: */
dd41f596 5148 activate_idle_task(p, rq);
1da177e4
LT
5149
5150 spin_unlock_irqrestore(&rq->lock, flags);
5151}
5152
48f24c4d
IM
5153/*
5154 * Ensures that the idle task is using init_mm right before its cpu goes
1da177e4
LT
5155 * offline.
5156 */
5157void idle_task_exit(void)
5158{
5159 struct mm_struct *mm = current->active_mm;
5160
5161 BUG_ON(cpu_online(smp_processor_id()));
5162
5163 if (mm != &init_mm)
5164 switch_mm(mm, &init_mm, current);
5165 mmdrop(mm);
5166}
5167
054b9108 5168/* called under rq->lock with disabled interrupts */
36c8b586 5169static void migrate_dead(unsigned int dead_cpu, struct task_struct *p)
1da177e4 5170{
70b97a7f 5171 struct rq *rq = cpu_rq(dead_cpu);
1da177e4
LT
5172
5173 /* Must be exiting, otherwise would be on tasklist. */
48f24c4d 5174 BUG_ON(p->exit_state != EXIT_ZOMBIE && p->exit_state != EXIT_DEAD);
1da177e4
LT
5175
5176 /* Cannot have done final schedule yet: would have vanished. */
c394cc9f 5177 BUG_ON(p->state == TASK_DEAD);
1da177e4 5178
48f24c4d 5179 get_task_struct(p);
1da177e4
LT
5180
5181 /*
5182 * Drop lock around migration; if someone else moves it,
5183 * that's OK. No task can be added to this CPU, so iteration is
5184 * fine.
054b9108 5185 * NOTE: interrupts should be left disabled --dev@
1da177e4 5186 */
054b9108 5187 spin_unlock(&rq->lock);
48f24c4d 5188 move_task_off_dead_cpu(dead_cpu, p);
054b9108 5189 spin_lock(&rq->lock);
1da177e4 5190
48f24c4d 5191 put_task_struct(p);
1da177e4
LT
5192}
5193
5194/* release_task() removes task from tasklist, so we won't find dead tasks. */
5195static void migrate_dead_tasks(unsigned int dead_cpu)
5196{
70b97a7f 5197 struct rq *rq = cpu_rq(dead_cpu);
dd41f596 5198 struct task_struct *next;
48f24c4d 5199
dd41f596
IM
5200 for ( ; ; ) {
5201 if (!rq->nr_running)
5202 break;
a8e504d2 5203 update_rq_clock(rq);
ff95f3df 5204 next = pick_next_task(rq, rq->curr);
dd41f596
IM
5205 if (!next)
5206 break;
5207 migrate_dead(dead_cpu, next);
e692ab53 5208
1da177e4
LT
5209 }
5210}
5211#endif /* CONFIG_HOTPLUG_CPU */
5212
e692ab53
NP
5213#if defined(CONFIG_SCHED_DEBUG) && defined(CONFIG_SYSCTL)
5214
5215static struct ctl_table sd_ctl_dir[] = {
e0361851
AD
5216 {
5217 .procname = "sched_domain",
5218 .mode = 0755,
5219 },
e692ab53
NP
5220 {0,},
5221};
5222
5223static struct ctl_table sd_ctl_root[] = {
e0361851
AD
5224 {
5225 .procname = "kernel",
5226 .mode = 0755,
5227 .child = sd_ctl_dir,
5228 },
e692ab53
NP
5229 {0,},
5230};
5231
5232static struct ctl_table *sd_alloc_ctl_entry(int n)
5233{
5234 struct ctl_table *entry =
5235 kmalloc(n * sizeof(struct ctl_table), GFP_KERNEL);
5236
5237 BUG_ON(!entry);
5238 memset(entry, 0, n * sizeof(struct ctl_table));
5239
5240 return entry;
5241}
5242
5243static void
e0361851 5244set_table_entry(struct ctl_table *entry,
e692ab53
NP
5245 const char *procname, void *data, int maxlen,
5246 mode_t mode, proc_handler *proc_handler)
5247{
e692ab53
NP
5248 entry->procname = procname;
5249 entry->data = data;
5250 entry->maxlen = maxlen;
5251 entry->mode = mode;
5252 entry->proc_handler = proc_handler;
5253}
5254
5255static struct ctl_table *
5256sd_alloc_ctl_domain_table(struct sched_domain *sd)
5257{
5258 struct ctl_table *table = sd_alloc_ctl_entry(14);
5259
e0361851 5260 set_table_entry(&table[0], "min_interval", &sd->min_interval,
e692ab53 5261 sizeof(long), 0644, proc_doulongvec_minmax);
e0361851 5262 set_table_entry(&table[1], "max_interval", &sd->max_interval,
e692ab53 5263 sizeof(long), 0644, proc_doulongvec_minmax);
e0361851 5264 set_table_entry(&table[2], "busy_idx", &sd->busy_idx,
e692ab53 5265 sizeof(int), 0644, proc_dointvec_minmax);
e0361851 5266 set_table_entry(&table[3], "idle_idx", &sd->idle_idx,
e692ab53 5267 sizeof(int), 0644, proc_dointvec_minmax);
e0361851 5268 set_table_entry(&table[4], "newidle_idx", &sd->newidle_idx,
e692ab53 5269 sizeof(int), 0644, proc_dointvec_minmax);
e0361851 5270 set_table_entry(&table[5], "wake_idx", &sd->wake_idx,
e692ab53 5271 sizeof(int), 0644, proc_dointvec_minmax);
e0361851 5272 set_table_entry(&table[6], "forkexec_idx", &sd->forkexec_idx,
e692ab53 5273 sizeof(int), 0644, proc_dointvec_minmax);
e0361851 5274 set_table_entry(&table[7], "busy_factor", &sd->busy_factor,
e692ab53 5275 sizeof(int), 0644, proc_dointvec_minmax);
e0361851 5276 set_table_entry(&table[8], "imbalance_pct", &sd->imbalance_pct,
e692ab53 5277 sizeof(int), 0644, proc_dointvec_minmax);
e0361851 5278 set_table_entry(&table[10], "cache_nice_tries",
e692ab53
NP
5279 &sd->cache_nice_tries,
5280 sizeof(int), 0644, proc_dointvec_minmax);
e0361851 5281 set_table_entry(&table[12], "flags", &sd->flags,
e692ab53
NP
5282 sizeof(int), 0644, proc_dointvec_minmax);
5283
5284 return table;
5285}
5286
5287static ctl_table *sd_alloc_ctl_cpu_table(int cpu)
5288{
5289 struct ctl_table *entry, *table;
5290 struct sched_domain *sd;
5291 int domain_num = 0, i;
5292 char buf[32];
5293
5294 for_each_domain(cpu, sd)
5295 domain_num++;
5296 entry = table = sd_alloc_ctl_entry(domain_num + 1);
5297
5298 i = 0;
5299 for_each_domain(cpu, sd) {
5300 snprintf(buf, 32, "domain%d", i);
e692ab53
NP
5301 entry->procname = kstrdup(buf, GFP_KERNEL);
5302 entry->mode = 0755;
5303 entry->child = sd_alloc_ctl_domain_table(sd);
5304 entry++;
5305 i++;
5306 }
5307 return table;
5308}
5309
5310static struct ctl_table_header *sd_sysctl_header;
5311static void init_sched_domain_sysctl(void)
5312{
5313 int i, cpu_num = num_online_cpus();
5314 struct ctl_table *entry = sd_alloc_ctl_entry(cpu_num + 1);
5315 char buf[32];
5316
5317 sd_ctl_dir[0].child = entry;
5318
5319 for (i = 0; i < cpu_num; i++, entry++) {
5320 snprintf(buf, 32, "cpu%d", i);
e692ab53
NP
5321 entry->procname = kstrdup(buf, GFP_KERNEL);
5322 entry->mode = 0755;
5323 entry->child = sd_alloc_ctl_cpu_table(i);
5324 }
5325 sd_sysctl_header = register_sysctl_table(sd_ctl_root);
5326}
5327#else
5328static void init_sched_domain_sysctl(void)
5329{
5330}
5331#endif
5332
1da177e4
LT
5333/*
5334 * migration_call - callback that gets triggered when a CPU is added.
5335 * Here we can start up the necessary migration thread for the new CPU.
5336 */
48f24c4d
IM
5337static int __cpuinit
5338migration_call(struct notifier_block *nfb, unsigned long action, void *hcpu)
1da177e4 5339{
1da177e4 5340 struct task_struct *p;
48f24c4d 5341 int cpu = (long)hcpu;
1da177e4 5342 unsigned long flags;
70b97a7f 5343 struct rq *rq;
1da177e4
LT
5344
5345 switch (action) {
5be9361c
GS
5346 case CPU_LOCK_ACQUIRE:
5347 mutex_lock(&sched_hotcpu_mutex);
5348 break;
5349
1da177e4 5350 case CPU_UP_PREPARE:
8bb78442 5351 case CPU_UP_PREPARE_FROZEN:
dd41f596 5352 p = kthread_create(migration_thread, hcpu, "migration/%d", cpu);
1da177e4
LT
5353 if (IS_ERR(p))
5354 return NOTIFY_BAD;
1da177e4
LT
5355 kthread_bind(p, cpu);
5356 /* Must be high prio: stop_machine expects to yield to it. */
5357 rq = task_rq_lock(p, &flags);
dd41f596 5358 __setscheduler(rq, p, SCHED_FIFO, MAX_RT_PRIO-1);
1da177e4
LT
5359 task_rq_unlock(rq, &flags);
5360 cpu_rq(cpu)->migration_thread = p;
5361 break;
48f24c4d 5362
1da177e4 5363 case CPU_ONLINE:
8bb78442 5364 case CPU_ONLINE_FROZEN:
1da177e4
LT
5365 /* Strictly unneccessary, as first user will wake it. */
5366 wake_up_process(cpu_rq(cpu)->migration_thread);
5367 break;
48f24c4d 5368
1da177e4
LT
5369#ifdef CONFIG_HOTPLUG_CPU
5370 case CPU_UP_CANCELED:
8bb78442 5371 case CPU_UP_CANCELED_FROZEN:
fc75cdfa
HC
5372 if (!cpu_rq(cpu)->migration_thread)
5373 break;
1da177e4 5374 /* Unbind it from offline cpu so it can run. Fall thru. */
a4c4af7c
HC
5375 kthread_bind(cpu_rq(cpu)->migration_thread,
5376 any_online_cpu(cpu_online_map));
1da177e4
LT
5377 kthread_stop(cpu_rq(cpu)->migration_thread);
5378 cpu_rq(cpu)->migration_thread = NULL;
5379 break;
48f24c4d 5380
1da177e4 5381 case CPU_DEAD:
8bb78442 5382 case CPU_DEAD_FROZEN:
1da177e4
LT
5383 migrate_live_tasks(cpu);
5384 rq = cpu_rq(cpu);
5385 kthread_stop(rq->migration_thread);
5386 rq->migration_thread = NULL;
5387 /* Idle task back to normal (off runqueue, low prio) */
5388 rq = task_rq_lock(rq->idle, &flags);
a8e504d2 5389 update_rq_clock(rq);
2e1cb74a 5390 deactivate_task(rq, rq->idle, 0);
1da177e4 5391 rq->idle->static_prio = MAX_PRIO;
dd41f596
IM
5392 __setscheduler(rq, rq->idle, SCHED_NORMAL, 0);
5393 rq->idle->sched_class = &idle_sched_class;
1da177e4
LT
5394 migrate_dead_tasks(cpu);
5395 task_rq_unlock(rq, &flags);
5396 migrate_nr_uninterruptible(rq);
5397 BUG_ON(rq->nr_running != 0);
5398
5399 /* No need to migrate the tasks: it was best-effort if
5be9361c 5400 * they didn't take sched_hotcpu_mutex. Just wake up
1da177e4
LT
5401 * the requestors. */
5402 spin_lock_irq(&rq->lock);
5403 while (!list_empty(&rq->migration_queue)) {
70b97a7f
IM
5404 struct migration_req *req;
5405
1da177e4 5406 req = list_entry(rq->migration_queue.next,
70b97a7f 5407 struct migration_req, list);
1da177e4
LT
5408 list_del_init(&req->list);
5409 complete(&req->done);
5410 }
5411 spin_unlock_irq(&rq->lock);
5412 break;
5413#endif
5be9361c
GS
5414 case CPU_LOCK_RELEASE:
5415 mutex_unlock(&sched_hotcpu_mutex);
5416 break;
1da177e4
LT
5417 }
5418 return NOTIFY_OK;
5419}
5420
5421/* Register at highest priority so that task migration (migrate_all_tasks)
5422 * happens before everything else.
5423 */
26c2143b 5424static struct notifier_block __cpuinitdata migration_notifier = {
1da177e4
LT
5425 .notifier_call = migration_call,
5426 .priority = 10
5427};
5428
5429int __init migration_init(void)
5430{
5431 void *cpu = (void *)(long)smp_processor_id();
07dccf33 5432 int err;
48f24c4d
IM
5433
5434 /* Start one for the boot CPU: */
07dccf33
AM
5435 err = migration_call(&migration_notifier, CPU_UP_PREPARE, cpu);
5436 BUG_ON(err == NOTIFY_BAD);
1da177e4
LT
5437 migration_call(&migration_notifier, CPU_ONLINE, cpu);
5438 register_cpu_notifier(&migration_notifier);
48f24c4d 5439
1da177e4
LT
5440 return 0;
5441}
5442#endif
5443
5444#ifdef CONFIG_SMP
476f3534
CL
5445
5446/* Number of possible processor ids */
5447int nr_cpu_ids __read_mostly = NR_CPUS;
5448EXPORT_SYMBOL(nr_cpu_ids);
5449
1a20ff27 5450#undef SCHED_DOMAIN_DEBUG
1da177e4
LT
5451#ifdef SCHED_DOMAIN_DEBUG
5452static void sched_domain_debug(struct sched_domain *sd, int cpu)
5453{
5454 int level = 0;
5455
41c7ce9a
NP
5456 if (!sd) {
5457 printk(KERN_DEBUG "CPU%d attaching NULL sched-domain.\n", cpu);
5458 return;
5459 }
5460
1da177e4
LT
5461 printk(KERN_DEBUG "CPU%d attaching sched-domain:\n", cpu);
5462
5463 do {
5464 int i;
5465 char str[NR_CPUS];
5466 struct sched_group *group = sd->groups;
5467 cpumask_t groupmask;
5468
5469 cpumask_scnprintf(str, NR_CPUS, sd->span);
5470 cpus_clear(groupmask);
5471
5472 printk(KERN_DEBUG);
5473 for (i = 0; i < level + 1; i++)
5474 printk(" ");
5475 printk("domain %d: ", level);
5476
5477 if (!(sd->flags & SD_LOAD_BALANCE)) {
5478 printk("does not load-balance\n");
5479 if (sd->parent)
33859f7f
MOS
5480 printk(KERN_ERR "ERROR: !SD_LOAD_BALANCE domain"
5481 " has parent");
1da177e4
LT
5482 break;
5483 }
5484
5485 printk("span %s\n", str);
5486
5487 if (!cpu_isset(cpu, sd->span))
33859f7f
MOS
5488 printk(KERN_ERR "ERROR: domain->span does not contain "
5489 "CPU%d\n", cpu);
1da177e4 5490 if (!cpu_isset(cpu, group->cpumask))
33859f7f
MOS
5491 printk(KERN_ERR "ERROR: domain->groups does not contain"
5492 " CPU%d\n", cpu);
1da177e4
LT
5493
5494 printk(KERN_DEBUG);
5495 for (i = 0; i < level + 2; i++)
5496 printk(" ");
5497 printk("groups:");
5498 do {
5499 if (!group) {
5500 printk("\n");
5501 printk(KERN_ERR "ERROR: group is NULL\n");
5502 break;
5503 }
5504
5517d86b 5505 if (!group->__cpu_power) {
1da177e4 5506 printk("\n");
33859f7f
MOS
5507 printk(KERN_ERR "ERROR: domain->cpu_power not "
5508 "set\n");
1da177e4
LT
5509 }
5510
5511 if (!cpus_weight(group->cpumask)) {
5512 printk("\n");
5513 printk(KERN_ERR "ERROR: empty group\n");
5514 }
5515
5516 if (cpus_intersects(groupmask, group->cpumask)) {
5517 printk("\n");
5518 printk(KERN_ERR "ERROR: repeated CPUs\n");
5519 }
5520
5521 cpus_or(groupmask, groupmask, group->cpumask);
5522
5523 cpumask_scnprintf(str, NR_CPUS, group->cpumask);
5524 printk(" %s", str);
5525
5526 group = group->next;
5527 } while (group != sd->groups);
5528 printk("\n");
5529
5530 if (!cpus_equal(sd->span, groupmask))
33859f7f
MOS
5531 printk(KERN_ERR "ERROR: groups don't span "
5532 "domain->span\n");
1da177e4
LT
5533
5534 level++;
5535 sd = sd->parent;
33859f7f
MOS
5536 if (!sd)
5537 continue;
1da177e4 5538
33859f7f
MOS
5539 if (!cpus_subset(groupmask, sd->span))
5540 printk(KERN_ERR "ERROR: parent span is not a superset "
5541 "of domain->span\n");
1da177e4
LT
5542
5543 } while (sd);
5544}
5545#else
48f24c4d 5546# define sched_domain_debug(sd, cpu) do { } while (0)
1da177e4
LT
5547#endif
5548
1a20ff27 5549static int sd_degenerate(struct sched_domain *sd)
245af2c7
SS
5550{
5551 if (cpus_weight(sd->span) == 1)
5552 return 1;
5553
5554 /* Following flags need at least 2 groups */
5555 if (sd->flags & (SD_LOAD_BALANCE |
5556 SD_BALANCE_NEWIDLE |
5557 SD_BALANCE_FORK |
89c4710e
SS
5558 SD_BALANCE_EXEC |
5559 SD_SHARE_CPUPOWER |
5560 SD_SHARE_PKG_RESOURCES)) {
245af2c7
SS
5561 if (sd->groups != sd->groups->next)
5562 return 0;
5563 }
5564
5565 /* Following flags don't use groups */
5566 if (sd->flags & (SD_WAKE_IDLE |
5567 SD_WAKE_AFFINE |
5568 SD_WAKE_BALANCE))
5569 return 0;
5570
5571 return 1;
5572}
5573
48f24c4d
IM
5574static int
5575sd_parent_degenerate(struct sched_domain *sd, struct sched_domain *parent)
245af2c7
SS
5576{
5577 unsigned long cflags = sd->flags, pflags = parent->flags;
5578
5579 if (sd_degenerate(parent))
5580 return 1;
5581
5582 if (!cpus_equal(sd->span, parent->span))
5583 return 0;
5584
5585 /* Does parent contain flags not in child? */
5586 /* WAKE_BALANCE is a subset of WAKE_AFFINE */
5587 if (cflags & SD_WAKE_AFFINE)
5588 pflags &= ~SD_WAKE_BALANCE;
5589 /* Flags needing groups don't count if only 1 group in parent */
5590 if (parent->groups == parent->groups->next) {
5591 pflags &= ~(SD_LOAD_BALANCE |
5592 SD_BALANCE_NEWIDLE |
5593 SD_BALANCE_FORK |
89c4710e
SS
5594 SD_BALANCE_EXEC |
5595 SD_SHARE_CPUPOWER |
5596 SD_SHARE_PKG_RESOURCES);
245af2c7
SS
5597 }
5598 if (~cflags & pflags)
5599 return 0;
5600
5601 return 1;
5602}
5603
1da177e4
LT
5604/*
5605 * Attach the domain 'sd' to 'cpu' as its base domain. Callers must
5606 * hold the hotplug lock.
5607 */
9c1cfda2 5608static void cpu_attach_domain(struct sched_domain *sd, int cpu)
1da177e4 5609{
70b97a7f 5610 struct rq *rq = cpu_rq(cpu);
245af2c7
SS
5611 struct sched_domain *tmp;
5612
5613 /* Remove the sched domains which do not contribute to scheduling. */
5614 for (tmp = sd; tmp; tmp = tmp->parent) {
5615 struct sched_domain *parent = tmp->parent;
5616 if (!parent)
5617 break;
1a848870 5618 if (sd_parent_degenerate(tmp, parent)) {
245af2c7 5619 tmp->parent = parent->parent;
1a848870
SS
5620 if (parent->parent)
5621 parent->parent->child = tmp;
5622 }
245af2c7
SS
5623 }
5624
1a848870 5625 if (sd && sd_degenerate(sd)) {
245af2c7 5626 sd = sd->parent;
1a848870
SS
5627 if (sd)
5628 sd->child = NULL;
5629 }
1da177e4
LT
5630
5631 sched_domain_debug(sd, cpu);
5632
674311d5 5633 rcu_assign_pointer(rq->sd, sd);
1da177e4
LT
5634}
5635
5636/* cpus with isolated domains */
67af63a6 5637static cpumask_t cpu_isolated_map = CPU_MASK_NONE;
1da177e4
LT
5638
5639/* Setup the mask of cpus configured for isolated domains */
5640static int __init isolated_cpu_setup(char *str)
5641{
5642 int ints[NR_CPUS], i;
5643
5644 str = get_options(str, ARRAY_SIZE(ints), ints);
5645 cpus_clear(cpu_isolated_map);
5646 for (i = 1; i <= ints[0]; i++)
5647 if (ints[i] < NR_CPUS)
5648 cpu_set(ints[i], cpu_isolated_map);
5649 return 1;
5650}
5651
5652__setup ("isolcpus=", isolated_cpu_setup);
5653
5654/*
6711cab4
SS
5655 * init_sched_build_groups takes the cpumask we wish to span, and a pointer
5656 * to a function which identifies what group(along with sched group) a CPU
5657 * belongs to. The return value of group_fn must be a >= 0 and < NR_CPUS
5658 * (due to the fact that we keep track of groups covered with a cpumask_t).
1da177e4
LT
5659 *
5660 * init_sched_build_groups will build a circular linked list of the groups
5661 * covered by the given span, and will set each group's ->cpumask correctly,
5662 * and ->cpu_power to 0.
5663 */
a616058b 5664static void
6711cab4
SS
5665init_sched_build_groups(cpumask_t span, const cpumask_t *cpu_map,
5666 int (*group_fn)(int cpu, const cpumask_t *cpu_map,
5667 struct sched_group **sg))
1da177e4
LT
5668{
5669 struct sched_group *first = NULL, *last = NULL;
5670 cpumask_t covered = CPU_MASK_NONE;
5671 int i;
5672
5673 for_each_cpu_mask(i, span) {
6711cab4
SS
5674 struct sched_group *sg;
5675 int group = group_fn(i, cpu_map, &sg);
1da177e4
LT
5676 int j;
5677
5678 if (cpu_isset(i, covered))
5679 continue;
5680
5681 sg->cpumask = CPU_MASK_NONE;
5517d86b 5682 sg->__cpu_power = 0;
1da177e4
LT
5683
5684 for_each_cpu_mask(j, span) {
6711cab4 5685 if (group_fn(j, cpu_map, NULL) != group)
1da177e4
LT
5686 continue;
5687
5688 cpu_set(j, covered);
5689 cpu_set(j, sg->cpumask);
5690 }
5691 if (!first)
5692 first = sg;
5693 if (last)
5694 last->next = sg;
5695 last = sg;
5696 }
5697 last->next = first;
5698}
5699
9c1cfda2 5700#define SD_NODES_PER_DOMAIN 16
1da177e4 5701
9c1cfda2 5702#ifdef CONFIG_NUMA
198e2f18 5703
9c1cfda2
JH
5704/**
5705 * find_next_best_node - find the next node to include in a sched_domain
5706 * @node: node whose sched_domain we're building
5707 * @used_nodes: nodes already in the sched_domain
5708 *
5709 * Find the next node to include in a given scheduling domain. Simply
5710 * finds the closest node not already in the @used_nodes map.
5711 *
5712 * Should use nodemask_t.
5713 */
5714static int find_next_best_node(int node, unsigned long *used_nodes)
5715{
5716 int i, n, val, min_val, best_node = 0;
5717
5718 min_val = INT_MAX;
5719
5720 for (i = 0; i < MAX_NUMNODES; i++) {
5721 /* Start at @node */
5722 n = (node + i) % MAX_NUMNODES;
5723
5724 if (!nr_cpus_node(n))
5725 continue;
5726
5727 /* Skip already used nodes */
5728 if (test_bit(n, used_nodes))
5729 continue;
5730
5731 /* Simple min distance search */
5732 val = node_distance(node, n);
5733
5734 if (val < min_val) {
5735 min_val = val;
5736 best_node = n;
5737 }
5738 }
5739
5740 set_bit(best_node, used_nodes);
5741 return best_node;
5742}
5743
5744/**
5745 * sched_domain_node_span - get a cpumask for a node's sched_domain
5746 * @node: node whose cpumask we're constructing
5747 * @size: number of nodes to include in this span
5748 *
5749 * Given a node, construct a good cpumask for its sched_domain to span. It
5750 * should be one that prevents unnecessary balancing, but also spreads tasks
5751 * out optimally.
5752 */
5753static cpumask_t sched_domain_node_span(int node)
5754{
9c1cfda2 5755 DECLARE_BITMAP(used_nodes, MAX_NUMNODES);
48f24c4d
IM
5756 cpumask_t span, nodemask;
5757 int i;
9c1cfda2
JH
5758
5759 cpus_clear(span);
5760 bitmap_zero(used_nodes, MAX_NUMNODES);
5761
5762 nodemask = node_to_cpumask(node);
5763 cpus_or(span, span, nodemask);
5764 set_bit(node, used_nodes);
5765
5766 for (i = 1; i < SD_NODES_PER_DOMAIN; i++) {
5767 int next_node = find_next_best_node(node, used_nodes);
48f24c4d 5768
9c1cfda2
JH
5769 nodemask = node_to_cpumask(next_node);
5770 cpus_or(span, span, nodemask);
5771 }
5772
5773 return span;
5774}
5775#endif
5776
5c45bf27 5777int sched_smt_power_savings = 0, sched_mc_power_savings = 0;
48f24c4d 5778
9c1cfda2 5779/*
48f24c4d 5780 * SMT sched-domains:
9c1cfda2 5781 */
1da177e4
LT
5782#ifdef CONFIG_SCHED_SMT
5783static DEFINE_PER_CPU(struct sched_domain, cpu_domains);
6711cab4 5784static DEFINE_PER_CPU(struct sched_group, sched_group_cpus);
48f24c4d 5785
6711cab4
SS
5786static int cpu_to_cpu_group(int cpu, const cpumask_t *cpu_map,
5787 struct sched_group **sg)
1da177e4 5788{
6711cab4
SS
5789 if (sg)
5790 *sg = &per_cpu(sched_group_cpus, cpu);
1da177e4
LT
5791 return cpu;
5792}
5793#endif
5794
48f24c4d
IM
5795/*
5796 * multi-core sched-domains:
5797 */
1e9f28fa
SS
5798#ifdef CONFIG_SCHED_MC
5799static DEFINE_PER_CPU(struct sched_domain, core_domains);
6711cab4 5800static DEFINE_PER_CPU(struct sched_group, sched_group_core);
1e9f28fa
SS
5801#endif
5802
5803#if defined(CONFIG_SCHED_MC) && defined(CONFIG_SCHED_SMT)
6711cab4
SS
5804static int cpu_to_core_group(int cpu, const cpumask_t *cpu_map,
5805 struct sched_group **sg)
1e9f28fa 5806{
6711cab4 5807 int group;
a616058b
SS
5808 cpumask_t mask = cpu_sibling_map[cpu];
5809 cpus_and(mask, mask, *cpu_map);
6711cab4
SS
5810 group = first_cpu(mask);
5811 if (sg)
5812 *sg = &per_cpu(sched_group_core, group);
5813 return group;
1e9f28fa
SS
5814}
5815#elif defined(CONFIG_SCHED_MC)
6711cab4
SS
5816static int cpu_to_core_group(int cpu, const cpumask_t *cpu_map,
5817 struct sched_group **sg)
1e9f28fa 5818{
6711cab4
SS
5819 if (sg)
5820 *sg = &per_cpu(sched_group_core, cpu);
1e9f28fa
SS
5821 return cpu;
5822}
5823#endif
5824
1da177e4 5825static DEFINE_PER_CPU(struct sched_domain, phys_domains);
6711cab4 5826static DEFINE_PER_CPU(struct sched_group, sched_group_phys);
48f24c4d 5827
6711cab4
SS
5828static int cpu_to_phys_group(int cpu, const cpumask_t *cpu_map,
5829 struct sched_group **sg)
1da177e4 5830{
6711cab4 5831 int group;
48f24c4d 5832#ifdef CONFIG_SCHED_MC
1e9f28fa 5833 cpumask_t mask = cpu_coregroup_map(cpu);
a616058b 5834 cpus_and(mask, mask, *cpu_map);
6711cab4 5835 group = first_cpu(mask);
1e9f28fa 5836#elif defined(CONFIG_SCHED_SMT)
a616058b
SS
5837 cpumask_t mask = cpu_sibling_map[cpu];
5838 cpus_and(mask, mask, *cpu_map);
6711cab4 5839 group = first_cpu(mask);
1da177e4 5840#else
6711cab4 5841 group = cpu;
1da177e4 5842#endif
6711cab4
SS
5843 if (sg)
5844 *sg = &per_cpu(sched_group_phys, group);
5845 return group;
1da177e4
LT
5846}
5847
5848#ifdef CONFIG_NUMA
1da177e4 5849/*
9c1cfda2
JH
5850 * The init_sched_build_groups can't handle what we want to do with node
5851 * groups, so roll our own. Now each node has its own list of groups which
5852 * gets dynamically allocated.
1da177e4 5853 */
9c1cfda2 5854static DEFINE_PER_CPU(struct sched_domain, node_domains);
d1b55138 5855static struct sched_group **sched_group_nodes_bycpu[NR_CPUS];
1da177e4 5856
9c1cfda2 5857static DEFINE_PER_CPU(struct sched_domain, allnodes_domains);
6711cab4 5858static DEFINE_PER_CPU(struct sched_group, sched_group_allnodes);
9c1cfda2 5859
6711cab4
SS
5860static int cpu_to_allnodes_group(int cpu, const cpumask_t *cpu_map,
5861 struct sched_group **sg)
9c1cfda2 5862{
6711cab4
SS
5863 cpumask_t nodemask = node_to_cpumask(cpu_to_node(cpu));
5864 int group;
5865
5866 cpus_and(nodemask, nodemask, *cpu_map);
5867 group = first_cpu(nodemask);
5868
5869 if (sg)
5870 *sg = &per_cpu(sched_group_allnodes, group);
5871 return group;
1da177e4 5872}
6711cab4 5873
08069033
SS
5874static void init_numa_sched_groups_power(struct sched_group *group_head)
5875{
5876 struct sched_group *sg = group_head;
5877 int j;
5878
5879 if (!sg)
5880 return;
5881next_sg:
5882 for_each_cpu_mask(j, sg->cpumask) {
5883 struct sched_domain *sd;
5884
5885 sd = &per_cpu(phys_domains, j);
5886 if (j != first_cpu(sd->groups->cpumask)) {
5887 /*
5888 * Only add "power" once for each
5889 * physical package.
5890 */
5891 continue;
5892 }
5893
5517d86b 5894 sg_inc_cpu_power(sg, sd->groups->__cpu_power);
08069033
SS
5895 }
5896 sg = sg->next;
5897 if (sg != group_head)
5898 goto next_sg;
5899}
1da177e4
LT
5900#endif
5901
a616058b 5902#ifdef CONFIG_NUMA
51888ca2
SV
5903/* Free memory allocated for various sched_group structures */
5904static void free_sched_groups(const cpumask_t *cpu_map)
5905{
a616058b 5906 int cpu, i;
51888ca2
SV
5907
5908 for_each_cpu_mask(cpu, *cpu_map) {
51888ca2
SV
5909 struct sched_group **sched_group_nodes
5910 = sched_group_nodes_bycpu[cpu];
5911
51888ca2
SV
5912 if (!sched_group_nodes)
5913 continue;
5914
5915 for (i = 0; i < MAX_NUMNODES; i++) {
5916 cpumask_t nodemask = node_to_cpumask(i);
5917 struct sched_group *oldsg, *sg = sched_group_nodes[i];
5918
5919 cpus_and(nodemask, nodemask, *cpu_map);
5920 if (cpus_empty(nodemask))
5921 continue;
5922
5923 if (sg == NULL)
5924 continue;
5925 sg = sg->next;
5926next_sg:
5927 oldsg = sg;
5928 sg = sg->next;
5929 kfree(oldsg);
5930 if (oldsg != sched_group_nodes[i])
5931 goto next_sg;
5932 }
5933 kfree(sched_group_nodes);
5934 sched_group_nodes_bycpu[cpu] = NULL;
5935 }
51888ca2 5936}
a616058b
SS
5937#else
5938static void free_sched_groups(const cpumask_t *cpu_map)
5939{
5940}
5941#endif
51888ca2 5942
89c4710e
SS
5943/*
5944 * Initialize sched groups cpu_power.
5945 *
5946 * cpu_power indicates the capacity of sched group, which is used while
5947 * distributing the load between different sched groups in a sched domain.
5948 * Typically cpu_power for all the groups in a sched domain will be same unless
5949 * there are asymmetries in the topology. If there are asymmetries, group
5950 * having more cpu_power will pickup more load compared to the group having
5951 * less cpu_power.
5952 *
5953 * cpu_power will be a multiple of SCHED_LOAD_SCALE. This multiple represents
5954 * the maximum number of tasks a group can handle in the presence of other idle
5955 * or lightly loaded groups in the same sched domain.
5956 */
5957static void init_sched_groups_power(int cpu, struct sched_domain *sd)
5958{
5959 struct sched_domain *child;
5960 struct sched_group *group;
5961
5962 WARN_ON(!sd || !sd->groups);
5963
5964 if (cpu != first_cpu(sd->groups->cpumask))
5965 return;
5966
5967 child = sd->child;
5968
5517d86b
ED
5969 sd->groups->__cpu_power = 0;
5970
89c4710e
SS
5971 /*
5972 * For perf policy, if the groups in child domain share resources
5973 * (for example cores sharing some portions of the cache hierarchy
5974 * or SMT), then set this domain groups cpu_power such that each group
5975 * can handle only one task, when there are other idle groups in the
5976 * same sched domain.
5977 */
5978 if (!child || (!(sd->flags & SD_POWERSAVINGS_BALANCE) &&
5979 (child->flags &
5980 (SD_SHARE_CPUPOWER | SD_SHARE_PKG_RESOURCES)))) {
5517d86b 5981 sg_inc_cpu_power(sd->groups, SCHED_LOAD_SCALE);
89c4710e
SS
5982 return;
5983 }
5984
89c4710e
SS
5985 /*
5986 * add cpu_power of each child group to this groups cpu_power
5987 */
5988 group = child->groups;
5989 do {
5517d86b 5990 sg_inc_cpu_power(sd->groups, group->__cpu_power);
89c4710e
SS
5991 group = group->next;
5992 } while (group != child->groups);
5993}
5994
1da177e4 5995/*
1a20ff27
DG
5996 * Build sched domains for a given set of cpus and attach the sched domains
5997 * to the individual cpus
1da177e4 5998 */
51888ca2 5999static int build_sched_domains(const cpumask_t *cpu_map)
1da177e4
LT
6000{
6001 int i;
d1b55138
JH
6002#ifdef CONFIG_NUMA
6003 struct sched_group **sched_group_nodes = NULL;
6711cab4 6004 int sd_allnodes = 0;
d1b55138
JH
6005
6006 /*
6007 * Allocate the per-node list of sched groups
6008 */
dd41f596 6009 sched_group_nodes = kzalloc(sizeof(struct sched_group *)*MAX_NUMNODES,
d3a5aa98 6010 GFP_KERNEL);
d1b55138
JH
6011 if (!sched_group_nodes) {
6012 printk(KERN_WARNING "Can not alloc sched group node list\n");
51888ca2 6013 return -ENOMEM;
d1b55138
JH
6014 }
6015 sched_group_nodes_bycpu[first_cpu(*cpu_map)] = sched_group_nodes;
6016#endif
1da177e4
LT
6017
6018 /*
1a20ff27 6019 * Set up domains for cpus specified by the cpu_map.
1da177e4 6020 */
1a20ff27 6021 for_each_cpu_mask(i, *cpu_map) {
1da177e4
LT
6022 struct sched_domain *sd = NULL, *p;
6023 cpumask_t nodemask = node_to_cpumask(cpu_to_node(i));
6024
1a20ff27 6025 cpus_and(nodemask, nodemask, *cpu_map);
1da177e4
LT
6026
6027#ifdef CONFIG_NUMA
dd41f596
IM
6028 if (cpus_weight(*cpu_map) >
6029 SD_NODES_PER_DOMAIN*cpus_weight(nodemask)) {
9c1cfda2
JH
6030 sd = &per_cpu(allnodes_domains, i);
6031 *sd = SD_ALLNODES_INIT;
6032 sd->span = *cpu_map;
6711cab4 6033 cpu_to_allnodes_group(i, cpu_map, &sd->groups);
9c1cfda2 6034 p = sd;
6711cab4 6035 sd_allnodes = 1;
9c1cfda2
JH
6036 } else
6037 p = NULL;
6038
1da177e4 6039 sd = &per_cpu(node_domains, i);
1da177e4 6040 *sd = SD_NODE_INIT;
9c1cfda2
JH
6041 sd->span = sched_domain_node_span(cpu_to_node(i));
6042 sd->parent = p;
1a848870
SS
6043 if (p)
6044 p->child = sd;
9c1cfda2 6045 cpus_and(sd->span, sd->span, *cpu_map);
1da177e4
LT
6046#endif
6047
6048 p = sd;
6049 sd = &per_cpu(phys_domains, i);
1da177e4
LT
6050 *sd = SD_CPU_INIT;
6051 sd->span = nodemask;
6052 sd->parent = p;
1a848870
SS
6053 if (p)
6054 p->child = sd;
6711cab4 6055 cpu_to_phys_group(i, cpu_map, &sd->groups);
1da177e4 6056
1e9f28fa
SS
6057#ifdef CONFIG_SCHED_MC
6058 p = sd;
6059 sd = &per_cpu(core_domains, i);
1e9f28fa
SS
6060 *sd = SD_MC_INIT;
6061 sd->span = cpu_coregroup_map(i);
6062 cpus_and(sd->span, sd->span, *cpu_map);
6063 sd->parent = p;
1a848870 6064 p->child = sd;
6711cab4 6065 cpu_to_core_group(i, cpu_map, &sd->groups);
1e9f28fa
SS
6066#endif
6067
1da177e4
LT
6068#ifdef CONFIG_SCHED_SMT
6069 p = sd;
6070 sd = &per_cpu(cpu_domains, i);
1da177e4
LT
6071 *sd = SD_SIBLING_INIT;
6072 sd->span = cpu_sibling_map[i];
1a20ff27 6073 cpus_and(sd->span, sd->span, *cpu_map);
1da177e4 6074 sd->parent = p;
1a848870 6075 p->child = sd;
6711cab4 6076 cpu_to_cpu_group(i, cpu_map, &sd->groups);
1da177e4
LT
6077#endif
6078 }
6079
6080#ifdef CONFIG_SCHED_SMT
6081 /* Set up CPU (sibling) groups */
9c1cfda2 6082 for_each_cpu_mask(i, *cpu_map) {
1da177e4 6083 cpumask_t this_sibling_map = cpu_sibling_map[i];
1a20ff27 6084 cpus_and(this_sibling_map, this_sibling_map, *cpu_map);
1da177e4
LT
6085 if (i != first_cpu(this_sibling_map))
6086 continue;
6087
dd41f596
IM
6088 init_sched_build_groups(this_sibling_map, cpu_map,
6089 &cpu_to_cpu_group);
1da177e4
LT
6090 }
6091#endif
6092
1e9f28fa
SS
6093#ifdef CONFIG_SCHED_MC
6094 /* Set up multi-core groups */
6095 for_each_cpu_mask(i, *cpu_map) {
6096 cpumask_t this_core_map = cpu_coregroup_map(i);
6097 cpus_and(this_core_map, this_core_map, *cpu_map);
6098 if (i != first_cpu(this_core_map))
6099 continue;
dd41f596
IM
6100 init_sched_build_groups(this_core_map, cpu_map,
6101 &cpu_to_core_group);
1e9f28fa
SS
6102 }
6103#endif
6104
1da177e4
LT
6105 /* Set up physical groups */
6106 for (i = 0; i < MAX_NUMNODES; i++) {
6107 cpumask_t nodemask = node_to_cpumask(i);
6108
1a20ff27 6109 cpus_and(nodemask, nodemask, *cpu_map);
1da177e4
LT
6110 if (cpus_empty(nodemask))
6111 continue;
6112
6711cab4 6113 init_sched_build_groups(nodemask, cpu_map, &cpu_to_phys_group);
1da177e4
LT
6114 }
6115
6116#ifdef CONFIG_NUMA
6117 /* Set up node groups */
6711cab4 6118 if (sd_allnodes)
dd41f596
IM
6119 init_sched_build_groups(*cpu_map, cpu_map,
6120 &cpu_to_allnodes_group);
9c1cfda2
JH
6121
6122 for (i = 0; i < MAX_NUMNODES; i++) {
6123 /* Set up node groups */
6124 struct sched_group *sg, *prev;
6125 cpumask_t nodemask = node_to_cpumask(i);
6126 cpumask_t domainspan;
6127 cpumask_t covered = CPU_MASK_NONE;
6128 int j;
6129
6130 cpus_and(nodemask, nodemask, *cpu_map);
d1b55138
JH
6131 if (cpus_empty(nodemask)) {
6132 sched_group_nodes[i] = NULL;
9c1cfda2 6133 continue;
d1b55138 6134 }
9c1cfda2
JH
6135
6136 domainspan = sched_domain_node_span(i);
6137 cpus_and(domainspan, domainspan, *cpu_map);
6138
15f0b676 6139 sg = kmalloc_node(sizeof(struct sched_group), GFP_KERNEL, i);
51888ca2
SV
6140 if (!sg) {
6141 printk(KERN_WARNING "Can not alloc domain group for "
6142 "node %d\n", i);
6143 goto error;
6144 }
9c1cfda2
JH
6145 sched_group_nodes[i] = sg;
6146 for_each_cpu_mask(j, nodemask) {
6147 struct sched_domain *sd;
9761eea8 6148
9c1cfda2
JH
6149 sd = &per_cpu(node_domains, j);
6150 sd->groups = sg;
9c1cfda2 6151 }
5517d86b 6152 sg->__cpu_power = 0;
9c1cfda2 6153 sg->cpumask = nodemask;
51888ca2 6154 sg->next = sg;
9c1cfda2
JH
6155 cpus_or(covered, covered, nodemask);
6156 prev = sg;
6157
6158 for (j = 0; j < MAX_NUMNODES; j++) {
6159 cpumask_t tmp, notcovered;
6160 int n = (i + j) % MAX_NUMNODES;
6161
6162 cpus_complement(notcovered, covered);
6163 cpus_and(tmp, notcovered, *cpu_map);
6164 cpus_and(tmp, tmp, domainspan);
6165 if (cpus_empty(tmp))
6166 break;
6167
6168 nodemask = node_to_cpumask(n);
6169 cpus_and(tmp, tmp, nodemask);
6170 if (cpus_empty(tmp))
6171 continue;
6172
15f0b676
SV
6173 sg = kmalloc_node(sizeof(struct sched_group),
6174 GFP_KERNEL, i);
9c1cfda2
JH
6175 if (!sg) {
6176 printk(KERN_WARNING
6177 "Can not alloc domain group for node %d\n", j);
51888ca2 6178 goto error;
9c1cfda2 6179 }
5517d86b 6180 sg->__cpu_power = 0;
9c1cfda2 6181 sg->cpumask = tmp;
51888ca2 6182 sg->next = prev->next;
9c1cfda2
JH
6183 cpus_or(covered, covered, tmp);
6184 prev->next = sg;
6185 prev = sg;
6186 }
9c1cfda2 6187 }
1da177e4
LT
6188#endif
6189
6190 /* Calculate CPU power for physical packages and nodes */
5c45bf27 6191#ifdef CONFIG_SCHED_SMT
1a20ff27 6192 for_each_cpu_mask(i, *cpu_map) {
dd41f596
IM
6193 struct sched_domain *sd = &per_cpu(cpu_domains, i);
6194
89c4710e 6195 init_sched_groups_power(i, sd);
5c45bf27 6196 }
1da177e4 6197#endif
1e9f28fa 6198#ifdef CONFIG_SCHED_MC
5c45bf27 6199 for_each_cpu_mask(i, *cpu_map) {
dd41f596
IM
6200 struct sched_domain *sd = &per_cpu(core_domains, i);
6201
89c4710e 6202 init_sched_groups_power(i, sd);
5c45bf27
SS
6203 }
6204#endif
1e9f28fa 6205
5c45bf27 6206 for_each_cpu_mask(i, *cpu_map) {
dd41f596
IM
6207 struct sched_domain *sd = &per_cpu(phys_domains, i);
6208
89c4710e 6209 init_sched_groups_power(i, sd);
1da177e4
LT
6210 }
6211
9c1cfda2 6212#ifdef CONFIG_NUMA
08069033
SS
6213 for (i = 0; i < MAX_NUMNODES; i++)
6214 init_numa_sched_groups_power(sched_group_nodes[i]);
9c1cfda2 6215
6711cab4
SS
6216 if (sd_allnodes) {
6217 struct sched_group *sg;
f712c0c7 6218
6711cab4 6219 cpu_to_allnodes_group(first_cpu(*cpu_map), cpu_map, &sg);
f712c0c7
SS
6220 init_numa_sched_groups_power(sg);
6221 }
9c1cfda2
JH
6222#endif
6223
1da177e4 6224 /* Attach the domains */
1a20ff27 6225 for_each_cpu_mask(i, *cpu_map) {
1da177e4
LT
6226 struct sched_domain *sd;
6227#ifdef CONFIG_SCHED_SMT
6228 sd = &per_cpu(cpu_domains, i);
1e9f28fa
SS
6229#elif defined(CONFIG_SCHED_MC)
6230 sd = &per_cpu(core_domains, i);
1da177e4
LT
6231#else
6232 sd = &per_cpu(phys_domains, i);
6233#endif
6234 cpu_attach_domain(sd, i);
6235 }
51888ca2
SV
6236
6237 return 0;
6238
a616058b 6239#ifdef CONFIG_NUMA
51888ca2
SV
6240error:
6241 free_sched_groups(cpu_map);
6242 return -ENOMEM;
a616058b 6243#endif
1da177e4 6244}
1a20ff27
DG
6245/*
6246 * Set up scheduler domains and groups. Callers must hold the hotplug lock.
6247 */
51888ca2 6248static int arch_init_sched_domains(const cpumask_t *cpu_map)
1a20ff27
DG
6249{
6250 cpumask_t cpu_default_map;
51888ca2 6251 int err;
1da177e4 6252
1a20ff27
DG
6253 /*
6254 * Setup mask for cpus without special case scheduling requirements.
6255 * For now this just excludes isolated cpus, but could be used to
6256 * exclude other special cases in the future.
6257 */
6258 cpus_andnot(cpu_default_map, *cpu_map, cpu_isolated_map);
6259
51888ca2
SV
6260 err = build_sched_domains(&cpu_default_map);
6261
6262 return err;
1a20ff27
DG
6263}
6264
6265static void arch_destroy_sched_domains(const cpumask_t *cpu_map)
1da177e4 6266{
51888ca2 6267 free_sched_groups(cpu_map);
9c1cfda2 6268}
1da177e4 6269
1a20ff27
DG
6270/*
6271 * Detach sched domains from a group of cpus specified in cpu_map
6272 * These cpus will now be attached to the NULL domain
6273 */
858119e1 6274static void detach_destroy_domains(const cpumask_t *cpu_map)
1a20ff27
DG
6275{
6276 int i;
6277
6278 for_each_cpu_mask(i, *cpu_map)
6279 cpu_attach_domain(NULL, i);
6280 synchronize_sched();
6281 arch_destroy_sched_domains(cpu_map);
6282}
6283
6284/*
6285 * Partition sched domains as specified by the cpumasks below.
6286 * This attaches all cpus from the cpumasks to the NULL domain,
6287 * waits for a RCU quiescent period, recalculates sched
6288 * domain information and then attaches them back to the
6289 * correct sched domains
6290 * Call with hotplug lock held
6291 */
51888ca2 6292int partition_sched_domains(cpumask_t *partition1, cpumask_t *partition2)
1a20ff27
DG
6293{
6294 cpumask_t change_map;
51888ca2 6295 int err = 0;
1a20ff27
DG
6296
6297 cpus_and(*partition1, *partition1, cpu_online_map);
6298 cpus_and(*partition2, *partition2, cpu_online_map);
6299 cpus_or(change_map, *partition1, *partition2);
6300
6301 /* Detach sched domains from all of the affected cpus */
6302 detach_destroy_domains(&change_map);
6303 if (!cpus_empty(*partition1))
51888ca2
SV
6304 err = build_sched_domains(partition1);
6305 if (!err && !cpus_empty(*partition2))
6306 err = build_sched_domains(partition2);
6307
6308 return err;
1a20ff27
DG
6309}
6310
5c45bf27
SS
6311#if defined(CONFIG_SCHED_MC) || defined(CONFIG_SCHED_SMT)
6312int arch_reinit_sched_domains(void)
6313{
6314 int err;
6315
5be9361c 6316 mutex_lock(&sched_hotcpu_mutex);
5c45bf27
SS
6317 detach_destroy_domains(&cpu_online_map);
6318 err = arch_init_sched_domains(&cpu_online_map);
5be9361c 6319 mutex_unlock(&sched_hotcpu_mutex);
5c45bf27
SS
6320
6321 return err;
6322}
6323
6324static ssize_t sched_power_savings_store(const char *buf, size_t count, int smt)
6325{
6326 int ret;
6327
6328 if (buf[0] != '0' && buf[0] != '1')
6329 return -EINVAL;
6330
6331 if (smt)
6332 sched_smt_power_savings = (buf[0] == '1');
6333 else
6334 sched_mc_power_savings = (buf[0] == '1');
6335
6336 ret = arch_reinit_sched_domains();
6337
6338 return ret ? ret : count;
6339}
6340
6341int sched_create_sysfs_power_savings_entries(struct sysdev_class *cls)
6342{
6343 int err = 0;
48f24c4d 6344
5c45bf27
SS
6345#ifdef CONFIG_SCHED_SMT
6346 if (smt_capable())
6347 err = sysfs_create_file(&cls->kset.kobj,
6348 &attr_sched_smt_power_savings.attr);
6349#endif
6350#ifdef CONFIG_SCHED_MC
6351 if (!err && mc_capable())
6352 err = sysfs_create_file(&cls->kset.kobj,
6353 &attr_sched_mc_power_savings.attr);
6354#endif
6355 return err;
6356}
6357#endif
6358
6359#ifdef CONFIG_SCHED_MC
6360static ssize_t sched_mc_power_savings_show(struct sys_device *dev, char *page)
6361{
6362 return sprintf(page, "%u\n", sched_mc_power_savings);
6363}
48f24c4d
IM
6364static ssize_t sched_mc_power_savings_store(struct sys_device *dev,
6365 const char *buf, size_t count)
5c45bf27
SS
6366{
6367 return sched_power_savings_store(buf, count, 0);
6368}
6369SYSDEV_ATTR(sched_mc_power_savings, 0644, sched_mc_power_savings_show,
6370 sched_mc_power_savings_store);
6371#endif
6372
6373#ifdef CONFIG_SCHED_SMT
6374static ssize_t sched_smt_power_savings_show(struct sys_device *dev, char *page)
6375{
6376 return sprintf(page, "%u\n", sched_smt_power_savings);
6377}
48f24c4d
IM
6378static ssize_t sched_smt_power_savings_store(struct sys_device *dev,
6379 const char *buf, size_t count)
5c45bf27
SS
6380{
6381 return sched_power_savings_store(buf, count, 1);
6382}
6383SYSDEV_ATTR(sched_smt_power_savings, 0644, sched_smt_power_savings_show,
6384 sched_smt_power_savings_store);
6385#endif
6386
1da177e4
LT
6387/*
6388 * Force a reinitialization of the sched domains hierarchy. The domains
6389 * and groups cannot be updated in place without racing with the balancing
41c7ce9a 6390 * code, so we temporarily attach all running cpus to the NULL domain
1da177e4
LT
6391 * which will prevent rebalancing while the sched domains are recalculated.
6392 */
6393static int update_sched_domains(struct notifier_block *nfb,
6394 unsigned long action, void *hcpu)
6395{
1da177e4
LT
6396 switch (action) {
6397 case CPU_UP_PREPARE:
8bb78442 6398 case CPU_UP_PREPARE_FROZEN:
1da177e4 6399 case CPU_DOWN_PREPARE:
8bb78442 6400 case CPU_DOWN_PREPARE_FROZEN:
1a20ff27 6401 detach_destroy_domains(&cpu_online_map);
1da177e4
LT
6402 return NOTIFY_OK;
6403
6404 case CPU_UP_CANCELED:
8bb78442 6405 case CPU_UP_CANCELED_FROZEN:
1da177e4 6406 case CPU_DOWN_FAILED:
8bb78442 6407 case CPU_DOWN_FAILED_FROZEN:
1da177e4 6408 case CPU_ONLINE:
8bb78442 6409 case CPU_ONLINE_FROZEN:
1da177e4 6410 case CPU_DEAD:
8bb78442 6411 case CPU_DEAD_FROZEN:
1da177e4
LT
6412 /*
6413 * Fall through and re-initialise the domains.
6414 */
6415 break;
6416 default:
6417 return NOTIFY_DONE;
6418 }
6419
6420 /* The hotplug lock is already held by cpu_up/cpu_down */
1a20ff27 6421 arch_init_sched_domains(&cpu_online_map);
1da177e4
LT
6422
6423 return NOTIFY_OK;
6424}
1da177e4
LT
6425
6426void __init sched_init_smp(void)
6427{
5c1e1767
NP
6428 cpumask_t non_isolated_cpus;
6429
5be9361c 6430 mutex_lock(&sched_hotcpu_mutex);
1a20ff27 6431 arch_init_sched_domains(&cpu_online_map);
e5e5673f 6432 cpus_andnot(non_isolated_cpus, cpu_possible_map, cpu_isolated_map);
5c1e1767
NP
6433 if (cpus_empty(non_isolated_cpus))
6434 cpu_set(smp_processor_id(), non_isolated_cpus);
5be9361c 6435 mutex_unlock(&sched_hotcpu_mutex);
1da177e4
LT
6436 /* XXX: Theoretical race here - CPU may be hotplugged now */
6437 hotcpu_notifier(update_sched_domains, 0);
5c1e1767 6438
e692ab53
NP
6439 init_sched_domain_sysctl();
6440
5c1e1767
NP
6441 /* Move init over to a non-isolated CPU */
6442 if (set_cpus_allowed(current, non_isolated_cpus) < 0)
6443 BUG();
dd41f596 6444 sched_init_granularity();
1da177e4
LT
6445}
6446#else
6447void __init sched_init_smp(void)
6448{
dd41f596 6449 sched_init_granularity();
1da177e4
LT
6450}
6451#endif /* CONFIG_SMP */
6452
6453int in_sched_functions(unsigned long addr)
6454{
6455 /* Linker adds these: start and end of __sched functions */
6456 extern char __sched_text_start[], __sched_text_end[];
48f24c4d 6457
1da177e4
LT
6458 return in_lock_functions(addr) ||
6459 (addr >= (unsigned long)__sched_text_start
6460 && addr < (unsigned long)__sched_text_end);
6461}
6462
dd41f596
IM
6463static inline void init_cfs_rq(struct cfs_rq *cfs_rq, struct rq *rq)
6464{
6465 cfs_rq->tasks_timeline = RB_ROOT;
6466 cfs_rq->fair_clock = 1;
6467#ifdef CONFIG_FAIR_GROUP_SCHED
6468 cfs_rq->rq = rq;
6469#endif
6470}
6471
1da177e4
LT
6472void __init sched_init(void)
6473{
dd41f596 6474 u64 now = sched_clock();
476f3534 6475 int highest_cpu = 0;
dd41f596
IM
6476 int i, j;
6477
6478 /*
6479 * Link up the scheduling class hierarchy:
6480 */
6481 rt_sched_class.next = &fair_sched_class;
6482 fair_sched_class.next = &idle_sched_class;
6483 idle_sched_class.next = NULL;
1da177e4 6484
0a945022 6485 for_each_possible_cpu(i) {
dd41f596 6486 struct rt_prio_array *array;
70b97a7f 6487 struct rq *rq;
1da177e4
LT
6488
6489 rq = cpu_rq(i);
6490 spin_lock_init(&rq->lock);
fcb99371 6491 lockdep_set_class(&rq->lock, &rq->rq_lock_key);
7897986b 6492 rq->nr_running = 0;
dd41f596
IM
6493 rq->clock = 1;
6494 init_cfs_rq(&rq->cfs, rq);
6495#ifdef CONFIG_FAIR_GROUP_SCHED
6496 INIT_LIST_HEAD(&rq->leaf_cfs_rq_list);
6497 list_add(&rq->cfs.leaf_cfs_rq_list, &rq->leaf_cfs_rq_list);
6498#endif
6499 rq->ls.load_update_last = now;
6500 rq->ls.load_update_start = now;
1da177e4 6501
dd41f596
IM
6502 for (j = 0; j < CPU_LOAD_IDX_MAX; j++)
6503 rq->cpu_load[j] = 0;
1da177e4 6504#ifdef CONFIG_SMP
41c7ce9a 6505 rq->sd = NULL;
1da177e4 6506 rq->active_balance = 0;
dd41f596 6507 rq->next_balance = jiffies;
1da177e4 6508 rq->push_cpu = 0;
0a2966b4 6509 rq->cpu = i;
1da177e4
LT
6510 rq->migration_thread = NULL;
6511 INIT_LIST_HEAD(&rq->migration_queue);
6512#endif
6513 atomic_set(&rq->nr_iowait, 0);
6514
dd41f596
IM
6515 array = &rq->rt.active;
6516 for (j = 0; j < MAX_RT_PRIO; j++) {
6517 INIT_LIST_HEAD(array->queue + j);
6518 __clear_bit(j, array->bitmap);
1da177e4 6519 }
476f3534 6520 highest_cpu = i;
dd41f596
IM
6521 /* delimiter for bitsearch: */
6522 __set_bit(MAX_RT_PRIO, array->bitmap);
1da177e4
LT
6523 }
6524
2dd73a4f 6525 set_load_weight(&init_task);
b50f60ce 6526
e107be36
AK
6527#ifdef CONFIG_PREEMPT_NOTIFIERS
6528 INIT_HLIST_HEAD(&init_task.preempt_notifiers);
6529#endif
6530
c9819f45 6531#ifdef CONFIG_SMP
476f3534 6532 nr_cpu_ids = highest_cpu + 1;
c9819f45
CL
6533 open_softirq(SCHED_SOFTIRQ, run_rebalance_domains, NULL);
6534#endif
6535
b50f60ce
HC
6536#ifdef CONFIG_RT_MUTEXES
6537 plist_head_init(&init_task.pi_waiters, &init_task.pi_lock);
6538#endif
6539
1da177e4
LT
6540 /*
6541 * The boot idle thread does lazy MMU switching as well:
6542 */
6543 atomic_inc(&init_mm.mm_count);
6544 enter_lazy_tlb(&init_mm, current);
6545
6546 /*
6547 * Make us the idle thread. Technically, schedule() should not be
6548 * called from this thread, however somewhere below it might be,
6549 * but because we are the idle thread, we just pick up running again
6550 * when this runqueue becomes "idle".
6551 */
6552 init_idle(current, smp_processor_id());
dd41f596
IM
6553 /*
6554 * During early bootup we pretend to be a normal task:
6555 */
6556 current->sched_class = &fair_sched_class;
1da177e4
LT
6557}
6558
6559#ifdef CONFIG_DEBUG_SPINLOCK_SLEEP
6560void __might_sleep(char *file, int line)
6561{
48f24c4d 6562#ifdef in_atomic
1da177e4
LT
6563 static unsigned long prev_jiffy; /* ratelimiting */
6564
6565 if ((in_atomic() || irqs_disabled()) &&
6566 system_state == SYSTEM_RUNNING && !oops_in_progress) {
6567 if (time_before(jiffies, prev_jiffy + HZ) && prev_jiffy)
6568 return;
6569 prev_jiffy = jiffies;
91368d73 6570 printk(KERN_ERR "BUG: sleeping function called from invalid"
1da177e4
LT
6571 " context at %s:%d\n", file, line);
6572 printk("in_atomic():%d, irqs_disabled():%d\n",
6573 in_atomic(), irqs_disabled());
a4c410f0 6574 debug_show_held_locks(current);
3117df04
IM
6575 if (irqs_disabled())
6576 print_irqtrace_events(current);
1da177e4
LT
6577 dump_stack();
6578 }
6579#endif
6580}
6581EXPORT_SYMBOL(__might_sleep);
6582#endif
6583
6584#ifdef CONFIG_MAGIC_SYSRQ
6585void normalize_rt_tasks(void)
6586{
a0f98a1c 6587 struct task_struct *g, *p;
1da177e4 6588 unsigned long flags;
70b97a7f 6589 struct rq *rq;
dd41f596 6590 int on_rq;
1da177e4
LT
6591
6592 read_lock_irq(&tasklist_lock);
a0f98a1c 6593 do_each_thread(g, p) {
dd41f596
IM
6594 p->se.fair_key = 0;
6595 p->se.wait_runtime = 0;
6cfb0d5d 6596 p->se.exec_start = 0;
dd41f596 6597 p->se.wait_start_fair = 0;
6cfb0d5d
IM
6598 p->se.sleep_start_fair = 0;
6599#ifdef CONFIG_SCHEDSTATS
dd41f596 6600 p->se.wait_start = 0;
dd41f596 6601 p->se.sleep_start = 0;
dd41f596 6602 p->se.block_start = 0;
6cfb0d5d 6603#endif
dd41f596
IM
6604 task_rq(p)->cfs.fair_clock = 0;
6605 task_rq(p)->clock = 0;
6606
6607 if (!rt_task(p)) {
6608 /*
6609 * Renice negative nice level userspace
6610 * tasks back to 0:
6611 */
6612 if (TASK_NICE(p) < 0 && p->mm)
6613 set_user_nice(p, 0);
1da177e4 6614 continue;
dd41f596 6615 }
1da177e4 6616
b29739f9
IM
6617 spin_lock_irqsave(&p->pi_lock, flags);
6618 rq = __task_rq_lock(p);
dd41f596
IM
6619#ifdef CONFIG_SMP
6620 /*
6621 * Do not touch the migration thread:
6622 */
6623 if (p == rq->migration_thread)
6624 goto out_unlock;
6625#endif
1da177e4 6626
dd41f596 6627 on_rq = p->se.on_rq;
a8e504d2
IM
6628 if (on_rq) {
6629 update_rq_clock(task_rq(p));
2e1cb74a 6630 deactivate_task(task_rq(p), p, 0);
a8e504d2 6631 }
dd41f596
IM
6632 __setscheduler(rq, p, SCHED_NORMAL, 0);
6633 if (on_rq) {
6634 activate_task(task_rq(p), p, 0);
1da177e4
LT
6635 resched_task(rq->curr);
6636 }
dd41f596
IM
6637#ifdef CONFIG_SMP
6638 out_unlock:
6639#endif
b29739f9
IM
6640 __task_rq_unlock(rq);
6641 spin_unlock_irqrestore(&p->pi_lock, flags);
a0f98a1c
IM
6642 } while_each_thread(g, p);
6643
1da177e4
LT
6644 read_unlock_irq(&tasklist_lock);
6645}
6646
6647#endif /* CONFIG_MAGIC_SYSRQ */
1df5c10a
LT
6648
6649#ifdef CONFIG_IA64
6650/*
6651 * These functions are only useful for the IA64 MCA handling.
6652 *
6653 * They can only be called when the whole system has been
6654 * stopped - every CPU needs to be quiescent, and no scheduling
6655 * activity can take place. Using them for anything else would
6656 * be a serious bug, and as a result, they aren't even visible
6657 * under any other configuration.
6658 */
6659
6660/**
6661 * curr_task - return the current task for a given cpu.
6662 * @cpu: the processor in question.
6663 *
6664 * ONLY VALID WHEN THE WHOLE SYSTEM IS STOPPED!
6665 */
36c8b586 6666struct task_struct *curr_task(int cpu)
1df5c10a
LT
6667{
6668 return cpu_curr(cpu);
6669}
6670
6671/**
6672 * set_curr_task - set the current task for a given cpu.
6673 * @cpu: the processor in question.
6674 * @p: the task pointer to set.
6675 *
6676 * Description: This function must only be used when non-maskable interrupts
6677 * are serviced on a separate stack. It allows the architecture to switch the
6678 * notion of the current task on a cpu in a non-blocking manner. This function
6679 * must be called with all CPU's synchronized, and interrupts disabled, the
6680 * and caller must save the original value of the current task (see
6681 * curr_task() above) and restore that value before reenabling interrupts and
6682 * re-starting the system.
6683 *
6684 * ONLY VALID WHEN THE WHOLE SYSTEM IS STOPPED!
6685 */
36c8b586 6686void set_curr_task(int cpu, struct task_struct *p)
1df5c10a
LT
6687{
6688 cpu_curr(cpu) = p;
6689}
6690
6691#endif
This page took 0.993311 seconds and 5 git commands to generate.