/* * kernel/sched.c * * Kernel scheduler and related syscalls * * Copyright (C) 1991-2002 Linus Torvalds * * 1996-12-23 Modified by Dave Grothe to fix bugs in semaphores and * make semaphores SMP safe * 1998-11-19 Implemented schedule_timeout() and related stuff * by Andrea Arcangeli * 2002-01-04 New ultra-scalable O(1) scheduler by Ingo Molnar: * hybrid priority-list and round-robin design with * an array-switch method of distributing timeslices * and per-CPU runqueues. Cleanups and useful suggestions * by Davide Libenzi, preemptible kernel bits by Robert Love. * 2003-09-03 Interactivity tuning by Con Kolivas. * 2004-04-02 Scheduler domains code by Nick Piggin * 2007-04-15 Work begun on replacing all interactivity tuning with a * fair scheduling design by Con Kolivas. * 2007-05-05 Load balancing (smp-nice) and other improvements * by Peter Williams * 2007-05-06 Interactivity improvements to CFS by Mike Galbraith * 2007-07-01 Group scheduling enhancements by Srivatsa Vaddagiri */ #include <linux/mm.h>#include <linux/module.h>#include <linux/nmi.h>#include <linux/init.h>#include <linux/uaccess.h>#include <linux/highmem.h>#include <linux/smp_lock.h>#include <asm/mmu_context.h>#include <linux/interrupt.h>#include <linux/capability.h>#include <linux/completion.h>#include <linux/kernel_stat.h>#include <linux/debug_locks.h>#include <linux/security.h>#include <linux/notifier.h>#include <linux/profile.h>#include <linux/freezer.h>#include <linux/vmalloc.h>#include <linux/blkdev.h>#include <linux/delay.h>#include <linux/pid_namespace.h>#include <linux/smp.h>#include <linux/threads.h>#include <linux/timer.h>#include <linux/rcupdate.h>#include <linux/cpu.h>#include <linux/cpuset.h>#include <linux/percpu.h>#include <linux/kthread.h>#include <linux/seq_file.h>#include <linux/sysctl.h>#include <linux/syscalls.h>#include <linux/times.h>#include <linux/tsacct_kern.h>#include <linux/kprobes.h>#include <linux/delayacct.h>#include <linux/reciprocal_div.h>#include <linux/unistd.h>#include <linux/pagemap.h> #include <asm/tlb.h>#include <asm/irq_regs.h> /* * Scheduler clock - returns current time in nanosec units. * This is default implementation. * Architectures and sub-architectures can override this. */unsigned long long __attribute__((weak)) sched_clock(void){ return (unsigned long long)jiffies * (NSEC_PER_SEC / HZ);} /* * Convert user-nice values [ -20 ... 0 ... 19 ] * to static priority [ MAX_RT_PRIO..MAX_PRIO-1 ], * and back. */#define NICE_TO_PRIO(nice) (MAX_RT_PRIO + (nice) + 20)#define PRIO_TO_NICE(prio) ((prio) - MAX_RT_PRIO - 20)#define TASK_NICE(p) PRIO_TO_NICE((p)->static_prio) /* * 'User priority' is the nice value converted to something we * can work with better when scaling various scheduler parameters, * it's a [ 0 ... 39 ] range. */#define USER_PRIO(p) ((p)-MAX_RT_PRIO)#define TASK_USER_PRIO(p) USER_PRIO((p)->static_prio)#define MAX_USER_PRIO (USER_PRIO(MAX_PRIO)) /* * Some helpers for converting nanosecond timing to jiffy resolution */#define NS_TO_JIFFIES(TIME) ((unsigned long)(TIME) / (NSEC_PER_SEC / HZ))#define JIFFIES_TO_NS(TIME) ((TIME) * (NSEC_PER_SEC / HZ)) #define NICE_0_LOAD SCHED_LOAD_SCALE#define NICE_0_SHIFT SCHED_LOAD_SHIFT /* * These are the 'tuning knobs' of the scheduler: * * default timeslice is 100 msecs (used only for SCHED_RR tasks). * Timeslices get refilled after they expire. */#define DEF_TIMESLICE (100 * HZ / 1000) #ifdef CONFIG_SMP/* * Divide a load by a sched group cpu_power : (load / sg->__cpu_power) * Since cpu_power is a 'constant', we can use a reciprocal divide. */static inline u32 sg_div_cpu_power(const struct sched_group *sg, u32 load){ return reciprocal_divide(load, sg->reciprocal_cpu_power);} /* * Each time a sched group cpu_power is changed, * we must compute its reciprocal value */static inline void sg_inc_cpu_power(struct sched_group *sg, u32 val){ sg->__cpu_power += val; sg->reciprocal_cpu_power = reciprocal_value(sg->__cpu_power);}#endif static inline int rt_policy(int policy){ if (unlikely(policy == SCHED_FIFO) || unlikely(policy == SCHED_RR)) return 1; return 0;} static inline int task_has_rt_policy(struct task_struct *p){ return rt_policy(p->policy);} /* * This is the priority-queue data structure of the RT scheduling class: */struct rt_prio_array { DECLARE_BITMAP(bitmap, MAX_RT_PRIO+1); /* include 1 bit for delimiter */ struct list_head queue[MAX_RT_PRIO];}; #ifdef CONFIG_FAIR_GROUP_SCHED #include <linux/cgroup.h> struct cfs_rq; /* task group related information */struct task_group {#ifdef CONFIG_FAIR_CGROUP_SCHED struct cgroup_subsys_state css;#endif /* schedulable entities of this group on each cpu */ struct sched_entity **se; /* runqueue "owned" by this group on each cpu */ struct cfs_rq **cfs_rq; unsigned long shares; /* spinlock to serialize modification to shares */ spinlock_t lock; struct rcu_head rcu;}; /* Default task group's sched entity on each cpu */static DEFINE_PER_CPU(struct sched_entity, init_sched_entity);/* Default task group's cfs_rq on each cpu */static DEFINE_PER_CPU(struct cfs_rq, init_cfs_rq) ____cacheline_aligned_in_smp; static struct sched_entity *init_sched_entity_p[NR_CPUS];static struct cfs_rq *init_cfs_rq_p[NR_CPUS]; /* Default task group. * Every task in system belong to this group at bootup. */struct task_group init_task_group = { .se = init_sched_entity_p, .cfs_rq = init_cfs_rq_p,}; #ifdef CONFIG_FAIR_USER_SCHED# define INIT_TASK_GRP_LOAD 2*NICE_0_LOAD#else# define INIT_TASK_GRP_LOAD NICE_0_LOAD#endif static int init_task_group_load = INIT_TASK_GRP_LOAD; /* return group to which a task belongs */static inline struct task_group *task_group(struct task_struct *p){ struct task_group *tg; #ifdef CONFIG_FAIR_USER_SCHED tg = p->user->tg;#elif defined(CONFIG_FAIR_CGROUP_SCHED) tg = container_of(task_subsys_state(p, cpu_cgroup_subsys_id), struct task_group, css);#else tg = &init_task_group;#endif return tg;} /* Change a task's cfs_rq and parent entity if it moves across CPUs/groups */static inline void set_task_cfs_rq(struct task_struct *p, unsigned int cpu){ p->se.cfs_rq = task_group(p)->cfs_rq[cpu]; p->se.parent = task_group(p)->se[cpu];} #else static inline void set_task_cfs_rq(struct task_struct *p, unsigned int cpu) { } #endif /* CONFIG_FAIR_GROUP_SCHED */ /* CFS-related fields in a runqueue */struct cfs_rq { struct load_weight load; unsigned long nr_running; u64 exec_clock; u64 min_vruntime; struct rb_root tasks_timeline; struct rb_node *rb_leftmost; struct rb_node *rb_load_balance_curr; /* 'curr' points to currently running entity on this cfs_rq. * It is set to NULL otherwise (i.e when none are currently running). */ struct sched_entity *curr; unsigned long nr_spread_over; #ifdef CONFIG_FAIR_GROUP_SCHED struct rq *rq; /* cpu runqueue to which this cfs_rq is attached */ /* * leaf cfs_rqs are those that hold tasks (lowest schedulable entity in * a hierarchy). Non-leaf lrqs hold other higher schedulable entities * (like users, containers etc.) * * leaf_cfs_rq_list ties together list of leaf cfs_rq's in a cpu. This * list is used during load balance. */ struct list_head leaf_cfs_rq_list; struct task_group *tg; /* group that "owns" this runqueue */#endif}; /* Real-Time classes' related field in a runqueue: */struct rt_rq { struct rt_prio_array active; int rt_load_balance_idx; struct list_head *rt_load_balance_head, *rt_load_balance_curr;}; /* * This is the main, per-CPU runqueue data structure. * * Locking rule: those places that want to lock multiple runqueues * (such as the load balancing or the thread migration code), lock * acquire operations must be ordered by ascending &runqueue. */struct rq { /* runqueue lock: */ spinlock_t lock; /* * nr_running and cpu_load should be in the same cacheline because * remote CPUs use both these fields when doing load calculation. */ unsigned long nr_running; #define CPU_LOAD_IDX_MAX 5 unsigned long cpu_load[CPU_LOAD_IDX_MAX]; unsigned char idle_at_tick;#ifdef CONFIG_NO_HZ unsigned char in_nohz_recently;#endif /* capture load from *all* tasks on this cpu: */ struct load_weight load; unsigned long nr_load_updates; u64 nr_switches; struct cfs_rq cfs;#ifdef CONFIG_FAIR_GROUP_SCHED /* list of leaf cfs_rq on this cpu: */ struct list_head leaf_cfs_rq_list;#endif struct rt_rq rt; /* * This is part of a global counter where only the total sum * over all CPUs matters. A task can increase this counter on * one CPU and if it got migrated afterwards it may decrease * it on another CPU. Always updated under the runqueue lock: */ unsigned long nr_uninterruptible; struct task_struct *curr, *idle; unsigned long next_balance; struct mm_struct *prev_mm; u64 clock, prev_clock_raw; s64 clock_max_delta; unsigned int clock_warps, clock_overflows; u64 idle_clock; unsigned int clock_deep_idle_events; u64 tick_timestamp; atomic_t nr_iowait; #ifdef CONFIG_SMP struct sched_domain *sd; /* For active balancing */ int active_balance; int push_cpu; /* cpu of this runqueue: */ int cpu; struct task_struct *migration_thread; struct list_head migration_queue;#endif #ifdef CONFIG_SCHEDSTATS /* latency stats */ struct sched_info rq_sched_info; /* sys_sched_yield() stats */ unsigned int yld_exp_empty; unsigned int yld_act_empty; unsigned int yld_both_empty; unsigned int yld_count; /* schedule() stats */ unsigned int sched_switch; unsigned int sched_count; unsigned int sched_goidle; /* try_to_wake_up() stats */ unsigned int ttwu_count; unsigned int ttwu_local; /* BKL stats */ unsigned int bkl_count;#endif struct lock_class_key rq_lock_key;}; static DEFINE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);static DEFINE_MUTEX(sched_hotcpu_mutex); static inline void check_preempt_curr(struct rq *rq, struct task_struct *p){ rq->curr->sched_class->check_preempt_curr(rq, p);} static inline int cpu_of(struct rq *rq){#ifdef CONFIG_SMP return rq->cpu;#else return 0;#endif} /* * Update the per-runqueue clock, as finegrained as the platform can give * us, but without assuming monotonicity, etc.: */static void __update_rq_clock(struct rq *rq){ u64 prev_raw = rq->prev_clock_raw; u64 now = sched_clock(); s64 delta = now - prev_raw; u64 clock = rq->clock; #ifdef CONFIG_SCHED_DEBUG WARN_ON_ONCE(cpu_of(rq) != smp_processor_id());#endif /* * Protect against sched_clock() occasionally going backwards: */ if (unlikely(delta < 0)) { clock++; rq->clock_warps++; } else { /* * Catch too large forward jumps too: */ if (unlikely(clock + delta > rq->tick_timestamp + TICK_NSEC)) { if (clock < rq->tick_timestamp + TICK_NSEC) clock = rq->tick_timestamp + TICK_NSEC; else clock++; rq->clock_overflows++; } else { if (unlikely(delta > rq->clock_max_delta)) rq->clock_max_delta = delta; clock += delta; } } rq->prev_clock_raw = now; rq->clock = clock;} static void update_rq_clock(struct rq *rq){ if (likely(smp_processor_id() == cpu_of(rq))) __update_rq_clock(rq);} /* * The domain tree (rq->sd) is protected by RCU's quiescent state transition. * See detach_destroy_domains: synchronize_sched for details. * * The domain tree of any CPU may only be accessed from within * preempt-disabled sections. */#define for_each_domain(cpu, __sd) \ for (__sd = rcu_dereference(cpu_rq(cpu)->sd); __sd; __sd = __sd->parent) #define cpu_rq(cpu) (&per_cpu(runqueues, (cpu)))#define this_rq() (&__get_cpu_var(runqueues))#define task_rq(p) cpu_rq(task_cpu(p))#define cpu_curr(cpu) (cpu_rq(cpu)->curr) /* * Tunables that become constants when CONFIG_SCHED_DEBUG is off: */#ifdef CONFIG_SCHED_DEBUG# define const_debug __read_mostly#else# define const_debug static const#endif /* * Debugging: various feature bits */enum { SCHED_FEAT_NEW_FAIR_SLEEPERS = 1, SCHED_FEAT_WAKEUP_PREEMPT = 2, SCHED_FEAT_START_DEBIT = 4, SCHED_FEAT_TREE_AVG = 8, SCHED_FEAT_APPROX_AVG = 16,}; const_debug unsigned int sysctl_sched_features = SCHED_FEAT_NEW_FAIR_SLEEPERS * 1 | SCHED_FEAT_WAKEUP_PREEMPT * 1 | SCHED_FEAT_START_DEBIT * 1 | SCHED_FEAT_TREE_AVG * 0 | SCHED_FEAT_APPROX_AVG * 0; #define sched_feat(x) (sysctl_sched_features & SCHED_FEAT_##x) /* * Number of tasks to iterate in a single balance run. * Limited because this is done with IRQs disabled. */const_debug unsigned int sysctl_sched_nr_migrate = 32; /* * For kernel-internal use: high-speed (but slightly incorrect) per-cpu * clock constructed from sched_clock(): */unsigned long long cpu_clock(int cpu){ unsigned long long now; unsigned long flags; struct rq *rq; local_irq_save(flags); rq = cpu_rq(cpu); /* * Only call sched_clock() if the scheduler has already been * initialized (some code might call cpu_clock() very early): */ if (rq->idle) update_rq_clock(rq); now = rq->clock; local_irq_restore(flags); return now;Lines 1–500 of 7404. Load more
/* * kernel/sched.c * * Kernel scheduler and related syscalls * * Copyright (C) 1991-2002 Linus Torvalds * * 1996-12-23 Modified by Dave Grothe to fix bugs in semaphores and * make semaphores SMP safe * 1998-11-19 Implemented schedule_timeout() and related stuff * by Andrea Arcangeli * 2002-01-04 New ultra-scalable O(1) scheduler by Ingo Molnar: * hybrid priority-list and round-robin design with * an array-switch method of distributing timeslices * and per-CPU runqueues. Cleanups and useful suggestions * by Davide Libenzi, preemptible kernel bits by Robert Love. * 2003-09-03 Interactivity tuning by Con Kolivas. * 2004-04-02 Scheduler domains code by Nick Piggin * 2007-04-15 Work begun on replacing all interactivity tuning with a * fair scheduling design by Con Kolivas. * 2007-05-05 Load balancing (smp-nice) and other improvements * by Peter Williams * 2007-05-06 Interactivity improvements to CFS by Mike Galbraith * 2007-07-01 Group scheduling enhancements by Srivatsa Vaddagiri */ #include <linux/mm.h> #include <linux/module.h> #include <linux/nmi.h> #include <linux/init.h> #include <linux/uaccess.h> #include <linux/highmem.h> #include <linux/smp_lock.h> #include <asm/mmu_context.h> #include <linux/interrupt.h> #include <linux/capability.h> #include <linux/completion.h> #include <linux/kernel_stat.h> #include <linux/debug_locks.h> #include <linux/security.h> #include <linux/notifier.h> #include <linux/profile.h> #include <linux/freezer.h> #include <linux/vmalloc.h> #include <linux/blkdev.h> #include <linux/delay.h> #include <linux/pid_namespace.h> #include <linux/smp.h> #include <linux/threads.h> #include <linux/timer.h> #include <linux/rcupdate.h> #include <linux/cpu.h> #include <linux/cpuset.h> #include <linux/percpu.h> #include <linux/kthread.h> #include <linux/seq_file.h> #include <linux/sysctl.h> #include <linux/syscalls.h> #include <linux/times.h> #include <linux/tsacct_kern.h> #include <linux/kprobes.h> #include <linux/delayacct.h> #include <linux/reciprocal_div.h> #include <linux/unistd.h> #include <linux/pagemap.h> #include <asm/tlb.h> #include <asm/irq_regs.h> /* * Scheduler clock - returns current time in nanosec units. * This is default implementation. * Architectures and sub-architectures can override this. */ unsigned long long __attribute__((weak)) sched_clock(void) { return (unsigned long long)jiffies * (NSEC_PER_SEC / HZ); } /* * Convert user-nice values [ -20 ... 0 ... 19 ] * to static priority [ MAX_RT_PRIO..MAX_PRIO-1 ], * and back. */ #define NICE_TO_PRIO(nice) (MAX_RT_PRIO + (nice) + 20) #define PRIO_TO_NICE(prio) ((prio) - MAX_RT_PRIO - 20) #define TASK_NICE(p) PRIO_TO_NICE((p)->static_prio) /* * 'User priority' is the nice value converted to something we * can work with better when scaling various scheduler parameters, * it's a [ 0 ... 39 ] range. */ #define USER_PRIO(p) ((p)-MAX_RT_PRIO) #define TASK_USER_PRIO(p) USER_PRIO((p)->static_prio) #define MAX_USER_PRIO (USER_PRIO(MAX_PRIO)) /* * Some helpers for converting nanosecond timing to jiffy resolution */ #define NS_TO_JIFFIES(TIME) ((unsigned long)(TIME) / (NSEC_PER_SEC / HZ)) #define JIFFIES_TO_NS(TIME) ((TIME) * (NSEC_PER_SEC / HZ)) #define NICE_0_LOAD SCHED_LOAD_SCALE #define NICE_0_SHIFT SCHED_LOAD_SHIFT /* * These are the 'tuning knobs' of the scheduler: * * default timeslice is 100 msecs (used only for SCHED_RR tasks). * Timeslices get refilled after they expire. */ #define DEF_TIMESLICE (100 * HZ / 1000) #ifdef CONFIG_SMP /* * Divide a load by a sched group cpu_power : (load / sg->__cpu_power) * Since cpu_power is a 'constant', we can use a reciprocal divide. */ static inline u32 sg_div_cpu_power(const struct sched_group *sg, u32 load) { return reciprocal_divide(load, sg->reciprocal_cpu_power); } /* * Each time a sched group cpu_power is changed, * we must compute its reciprocal value */ static inline void sg_inc_cpu_power(struct sched_group *sg, u32 val) { sg->__cpu_power += val; sg->reciprocal_cpu_power = reciprocal_value(sg->__cpu_power); } #endif static inline int rt_policy(int policy) { if (unlikely(policy == SCHED_FIFO) || unlikely(policy == SCHED_RR)) return 1; return 0; } static inline int task_has_rt_policy(struct task_struct *p) { return rt_policy(p->policy); } /* * This is the priority-queue data structure of the RT scheduling class: */ struct rt_prio_array { DECLARE_BITMAP(bitmap, MAX_RT_PRIO+1); /* include 1 bit for delimiter */ struct list_head queue[MAX_RT_PRIO]; }; #ifdef CONFIG_FAIR_GROUP_SCHED #include <linux/cgroup.h> struct cfs_rq; /* task group related information */ struct task_group { #ifdef CONFIG_FAIR_CGROUP_SCHED struct cgroup_subsys_state css; #endif /* schedulable entities of this group on each cpu */ struct sched_entity **se; /* runqueue "owned" by this group on each cpu */ struct cfs_rq **cfs_rq; unsigned long shares; /* spinlock to serialize modification to shares */ spinlock_t lock; struct rcu_head rcu; }; /* Default task group's sched entity on each cpu */ static DEFINE_PER_CPU(struct sched_entity, init_sched_entity); /* Default task group's cfs_rq on each cpu */ static DEFINE_PER_CPU(struct cfs_rq, init_cfs_rq) ____cacheline_aligned_in_smp; static struct sched_entity *init_sched_entity_p[NR_CPUS]; static struct cfs_rq *init_cfs_rq_p[NR_CPUS]; /* Default task group. * Every task in system belong to this group at bootup. */ struct task_group init_task_group = { .se = init_sched_entity_p, .cfs_rq = init_cfs_rq_p, }; #ifdef CONFIG_FAIR_USER_SCHED # define INIT_TASK_GRP_LOAD 2*NICE_0_LOAD #else # define INIT_TASK_GRP_LOAD NICE_0_LOAD #endif static int init_task_group_load = INIT_TASK_GRP_LOAD; /* return group to which a task belongs */ static inline struct task_group *task_group(struct task_struct *p) { struct task_group *tg; #ifdef CONFIG_FAIR_USER_SCHED tg = p->user->tg; #elif defined(CONFIG_FAIR_CGROUP_SCHED) tg = container_of(task_subsys_state(p, cpu_cgroup_subsys_id), struct task_group, css); #else tg = &init_task_group; #endif return tg; } /* Change a task's cfs_rq and parent entity if it moves across CPUs/groups */ static inline void set_task_cfs_rq(struct task_struct *p, unsigned int cpu) { p->se.cfs_rq = task_group(p)->cfs_rq[cpu]; p->se.parent = task_group(p)->se[cpu]; } #else static inline void set_task_cfs_rq(struct task_struct *p, unsigned int cpu) { } #endif /* CONFIG_FAIR_GROUP_SCHED */ /* CFS-related fields in a runqueue */ struct cfs_rq { struct load_weight load; unsigned long nr_running; u64 exec_clock; u64 min_vruntime; struct rb_root tasks_timeline; struct rb_node *rb_leftmost; struct rb_node *rb_load_balance_curr; /* 'curr' points to currently running entity on this cfs_rq. * It is set to NULL otherwise (i.e when none are currently running). */ struct sched_entity *curr; unsigned long nr_spread_over; #ifdef CONFIG_FAIR_GROUP_SCHED struct rq *rq; /* cpu runqueue to which this cfs_rq is attached */ /* * leaf cfs_rqs are those that hold tasks (lowest schedulable entity in * a hierarchy). Non-leaf lrqs hold other higher schedulable entities * (like users, containers etc.) * * leaf_cfs_rq_list ties together list of leaf cfs_rq's in a cpu. This * list is used during load balance. */ struct list_head leaf_cfs_rq_list; struct task_group *tg; /* group that "owns" this runqueue */ #endif }; /* Real-Time classes' related field in a runqueue: */ struct rt_rq { struct rt_prio_array active; int rt_load_balance_idx; struct list_head *rt_load_balance_head, *rt_load_balance_curr; }; /* * This is the main, per-CPU runqueue data structure. * * Locking rule: those places that want to lock multiple runqueues * (such as the load balancing or the thread migration code), lock * acquire operations must be ordered by ascending &runqueue. */ struct rq { /* runqueue lock: */ spinlock_t lock; /* * nr_running and cpu_load should be in the same cacheline because * remote CPUs use both these fields when doing load calculation. */ unsigned long nr_running; #define CPU_LOAD_IDX_MAX 5 unsigned long cpu_load[CPU_LOAD_IDX_MAX]; unsigned char idle_at_tick; #ifdef CONFIG_NO_HZ unsigned char in_nohz_recently; #endif /* capture load from *all* tasks on this cpu: */ struct load_weight load; unsigned long nr_load_updates; u64 nr_switches; struct cfs_rq cfs; #ifdef CONFIG_FAIR_GROUP_SCHED /* list of leaf cfs_rq on this cpu: */ struct list_head leaf_cfs_rq_list; #endif struct rt_rq rt; /* * This is part of a global counter where only the total sum * over all CPUs matters. A task can increase this counter on * one CPU and if it got migrated afterwards it may decrease * it on another CPU. Always updated under the runqueue lock: */ unsigned long nr_uninterruptible; struct task_struct *curr, *idle; unsigned long next_balance; struct mm_struct *prev_mm; u64 clock, prev_clock_raw; s64 clock_max_delta; unsigned int clock_warps, clock_overflows; u64 idle_clock; unsigned int clock_deep_idle_events; u64 tick_timestamp; atomic_t nr_iowait; #ifdef CONFIG_SMP struct sched_domain *sd; /* For active balancing */ int active_balance; int push_cpu; /* cpu of this runqueue: */ int cpu; struct task_struct *migration_thread; struct list_head migration_queue; #endif #ifdef CONFIG_SCHEDSTATS /* latency stats */ struct sched_info rq_sched_info; /* sys_sched_yield() stats */ unsigned int yld_exp_empty; unsigned int yld_act_empty; unsigned int yld_both_empty; unsigned int yld_count; /* schedule() stats */ unsigned int sched_switch; unsigned int sched_count; unsigned int sched_goidle; /* try_to_wake_up() stats */ unsigned int ttwu_count; unsigned int ttwu_local; /* BKL stats */ unsigned int bkl_count; #endif struct lock_class_key rq_lock_key; }; static DEFINE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues); static DEFINE_MUTEX(sched_hotcpu_mutex); static inline void check_preempt_curr(struct rq *rq, struct task_struct *p) { rq->curr->sched_class->check_preempt_curr(rq, p); } static inline int cpu_of(struct rq *rq) { #ifdef CONFIG_SMP return rq->cpu; #else return 0; #endif } /* * Update the per-runqueue clock, as finegrained as the platform can give * us, but without assuming monotonicity, etc.: */ static void __update_rq_clock(struct rq *rq) { u64 prev_raw = rq->prev_clock_raw; u64 now = sched_clock(); s64 delta = now - prev_raw; u64 clock = rq->clock; #ifdef CONFIG_SCHED_DEBUG WARN_ON_ONCE(cpu_of(rq) != smp_processor_id()); #endif /* * Protect against sched_clock() occasionally going backwards: */ if (unlikely(delta < 0)) { clock++; rq->clock_warps++; } else { /* * Catch too large forward jumps too: */ if (unlikely(clock + delta > rq->tick_timestamp + TICK_NSEC)) { if (clock < rq->tick_timestamp + TICK_NSEC) clock = rq->tick_timestamp + TICK_NSEC; else clock++; rq->clock_overflows++; } else { if (unlikely(delta > rq->clock_max_delta)) rq->clock_max_delta = delta; clock += delta; } } rq->prev_clock_raw = now; rq->clock = clock; } static void update_rq_clock(struct rq *rq) { if (likely(smp_processor_id() == cpu_of(rq))) __update_rq_clock(rq); } /* * The domain tree (rq->sd) is protected by RCU's quiescent state transition. * See detach_destroy_domains: synchronize_sched for details. * * The domain tree of any CPU may only be accessed from within * preempt-disabled sections. */ #define for_each_domain(cpu, __sd) \ for (__sd = rcu_dereference(cpu_rq(cpu)->sd); __sd; __sd = __sd->parent) #define cpu_rq(cpu) (&per_cpu(runqueues, (cpu))) #define this_rq() (&__get_cpu_var(runqueues)) #define task_rq(p) cpu_rq(task_cpu(p)) #define cpu_curr(cpu) (cpu_rq(cpu)->curr) /* * Tunables that become constants when CONFIG_SCHED_DEBUG is off: */ #ifdef CONFIG_SCHED_DEBUG # define const_debug __read_mostly #else # define const_debug static const #endif /* * Debugging: various feature bits */ enum { SCHED_FEAT_NEW_FAIR_SLEEPERS = 1, SCHED_FEAT_WAKEUP_PREEMPT = 2, SCHED_FEAT_START_DEBIT = 4, SCHED_FEAT_TREE_AVG = 8, SCHED_FEAT_APPROX_AVG = 16, }; const_debug unsigned int sysctl_sched_features = SCHED_FEAT_NEW_FAIR_SLEEPERS * 1 | SCHED_FEAT_WAKEUP_PREEMPT * 1 | SCHED_FEAT_START_DEBIT * 1 | SCHED_FEAT_TREE_AVG * 0 | SCHED_FEAT_APPROX_AVG * 0; #define sched_feat(x) (sysctl_sched_features & SCHED_FEAT_##x) /* * Number of tasks to iterate in a single balance run. * Limited because this is done with IRQs disabled. */ const_debug unsigned int sysctl_sched_nr_migrate = 32; /* * For kernel-internal use: high-speed (but slightly incorrect) per-cpu * clock constructed from sched_clock(): */ unsigned long long cpu_clock(int cpu) { unsigned long long now; unsigned long flags; struct rq *rq; local_irq_save(flags); rq = cpu_rq(cpu); /* * Only call sched_clock() if the scheduler has already been * initialized (some code might call cpu_clock() very early): */ if (rq->idle) update_rq_clock(rq); now = rq->clock; local_irq_restore(flags); return now;