From d15bcfdbe1818478891d714343f037cfe60875f0 Mon Sep 17 00:00:00 2001 From: Ingo Molnar Date: Mon, 9 Jul 2007 18:51:57 +0200 Subject: sched: rename idle_type/SCHED_IDLE enum idle_type (used by the load-balancer) clashes with the SCHED_IDLE name that we want to introduce. 'CPU_IDLE' instead of 'SCHED_IDLE' is more descriptive as well. Signed-off-by: Ingo Molnar --- include/linux/sched.h | 27 +++++++++++++-------------- 1 file changed, 13 insertions(+), 14 deletions(-) (limited to 'include/linux/sched.h') diff --git a/include/linux/sched.h b/include/linux/sched.h index 693f0e6c54d4..2acfb23f3681 100644 --- a/include/linux/sched.h +++ b/include/linux/sched.h @@ -639,12 +639,11 @@ static inline int sched_info_on(void) #endif } -enum idle_type -{ - SCHED_IDLE, - NOT_IDLE, - NEWLY_IDLE, - MAX_IDLE_TYPES +enum cpu_idle_type { + CPU_IDLE, + CPU_NOT_IDLE, + CPU_NEWLY_IDLE, + CPU_MAX_IDLE_TYPES }; /* @@ -719,14 +718,14 @@ struct sched_domain { #ifdef CONFIG_SCHEDSTATS /* load_balance() stats */ - unsigned long lb_cnt[MAX_IDLE_TYPES]; - unsigned long lb_failed[MAX_IDLE_TYPES]; - unsigned long lb_balanced[MAX_IDLE_TYPES]; - unsigned long lb_imbalance[MAX_IDLE_TYPES]; - unsigned long lb_gained[MAX_IDLE_TYPES]; - unsigned long lb_hot_gained[MAX_IDLE_TYPES]; - unsigned long lb_nobusyg[MAX_IDLE_TYPES]; - unsigned long lb_nobusyq[MAX_IDLE_TYPES]; + unsigned long lb_cnt[CPU_MAX_IDLE_TYPES]; + unsigned long lb_failed[CPU_MAX_IDLE_TYPES]; + unsigned long lb_balanced[CPU_MAX_IDLE_TYPES]; + unsigned long lb_imbalance[CPU_MAX_IDLE_TYPES]; + unsigned long lb_gained[CPU_MAX_IDLE_TYPES]; + unsigned long lb_hot_gained[CPU_MAX_IDLE_TYPES]; + unsigned long lb_nobusyg[CPU_MAX_IDLE_TYPES]; + unsigned long lb_nobusyq[CPU_MAX_IDLE_TYPES]; /* Active load balancing */ unsigned long alb_cnt; -- cgit v1.2.3 From 0e6aca43e08a62a48d6770e9a159dbec167bf4c6 Mon Sep 17 00:00:00 2001 From: Ingo Molnar Date: Mon, 9 Jul 2007 18:51:57 +0200 Subject: sched: add SCHED_IDLE policy this patch adds the SCHED_IDLE policy to sched.h. Signed-off-by: Ingo Molnar --- include/linux/sched.h | 2 ++ 1 file changed, 2 insertions(+) (limited to 'include/linux/sched.h') diff --git a/include/linux/sched.h b/include/linux/sched.h index 2acfb23f3681..7e74262f98e1 100644 --- a/include/linux/sched.h +++ b/include/linux/sched.h @@ -34,6 +34,8 @@ #define SCHED_FIFO 1 #define SCHED_RR 2 #define SCHED_BATCH 3 +/* SCHED_ISO: reserved but not implemented yet */ +#define SCHED_IDLE 5 #ifdef __KERNEL__ -- cgit v1.2.3 From 0437e109e1841607f2988891eaa36c531c6aa6ac Mon Sep 17 00:00:00 2001 From: Ingo Molnar Date: Mon, 9 Jul 2007 18:51:57 +0200 Subject: sched: zap the migration init / cache-hot balancing code the SMP load-balancer uses the boot-time migration-cost estimation code to attempt to improve the quality of balancing. The reason for this code is that the discrete priority queues do not preserve the order of scheduling accurately, so the load-balancer skips tasks that were running on a CPU 'recently'. this code is fundamental fragile: the boot-time migration cost detector doesnt really work on systems that had large L3 caches, it caused boot delays on large systems and the whole cache-hot concept made the balancing code pretty undeterministic as well. (and hey, i wrote most of it, so i can say it out loud that it sucks ;-) under CFS the same purpose of cache affinity can be achieved without any special cache-hot special-case: tasks are sorted in the 'timeline' tree and the SMP balancer picks tasks from the left side of the tree, thus the most cache-cold task is balanced automatically. Signed-off-by: Ingo Molnar --- Documentation/kernel-parameters.txt | 43 ---- arch/i386/kernel/smpboot.c | 12 - arch/ia64/kernel/setup.c | 6 - arch/mips/kernel/smp.c | 11 - arch/sparc/kernel/smp.c | 10 - arch/sparc64/kernel/smp.c | 27 -- include/linux/sched.h | 6 - kernel/sched.c | 481 ------------------------------------ 8 files changed, 596 deletions(-) (limited to 'include/linux/sched.h') diff --git a/Documentation/kernel-parameters.txt b/Documentation/kernel-parameters.txt index af50f9bbe68e..4d880b3d1f35 100644 --- a/Documentation/kernel-parameters.txt +++ b/Documentation/kernel-parameters.txt @@ -1014,49 +1014,6 @@ and is between 256 and 4096 characters. It is defined in the file mga= [HW,DRM] - migration_cost= - [KNL,SMP] debug: override scheduler migration costs - Format: ,,... - This debugging option can be used to override the - default scheduler migration cost matrix. The numbers - are indexed by 'CPU domain distance'. - E.g. migration_cost=1000,2000,3000 on an SMT NUMA - box will set up an intra-core migration cost of - 1 msec, an inter-core migration cost of 2 msecs, - and an inter-node migration cost of 3 msecs. - - WARNING: using the wrong values here can break - scheduler performance, so it's only for scheduler - development purposes, not production environments. - - migration_debug= - [KNL,SMP] migration cost auto-detect verbosity - Format=<0|1|2> - If a system's migration matrix reported at bootup - seems erroneous then this option can be used to - increase verbosity of the detection process. - We default to 0 (no extra messages), 1 will print - some more information, and 2 will be really - verbose (probably only useful if you also have a - serial console attached to the system). - - migration_factor= - [KNL,SMP] multiply/divide migration costs by a factor - Format= - This debug option can be used to proportionally - increase or decrease the auto-detected migration - costs for all entries of the migration matrix. - E.g. migration_factor=150 will increase migration - costs by 50%. (and thus the scheduler will be less - eager migrating cache-hot tasks) - migration_factor=80 will decrease migration costs - by 20%. (thus the scheduler will be more eager to - migrate tasks) - - WARNING: using the wrong values here can break - scheduler performance, so it's only for scheduler - development purposes, not production environments. - mousedev.tap_time= [MOUSE] Maximum time between finger touching and leaving touchpad surface for touch to be considered diff --git a/arch/i386/kernel/smpboot.c b/arch/i386/kernel/smpboot.c index 88baed1e7e83..0b2954534b8e 100644 --- a/arch/i386/kernel/smpboot.c +++ b/arch/i386/kernel/smpboot.c @@ -941,17 +941,6 @@ exit: } #endif -static void smp_tune_scheduling(void) -{ - if (cpu_khz) { - /* cache size in kB */ - long cachesize = boot_cpu_data.x86_cache_size; - - if (cachesize > 0) - max_cache_size = cachesize * 1024; - } -} - /* * Cycle through the processors sending APIC IPIs to boot each. */ @@ -980,7 +969,6 @@ static void __init smp_boot_cpus(unsigned int max_cpus) x86_cpu_to_apicid[0] = boot_cpu_physical_apicid; current_thread_info()->cpu = 0; - smp_tune_scheduling(); set_cpu_sibling_map(0); diff --git a/arch/ia64/kernel/setup.c b/arch/ia64/kernel/setup.c index eaa6a24bc0b6..188fb73c6845 100644 --- a/arch/ia64/kernel/setup.c +++ b/arch/ia64/kernel/setup.c @@ -805,7 +805,6 @@ static void __cpuinit get_max_cacheline_size (void) { unsigned long line_size, max = 1; - unsigned int cache_size = 0; u64 l, levels, unique_caches; pal_cache_config_info_t cci; s64 status; @@ -835,8 +834,6 @@ get_max_cacheline_size (void) line_size = 1 << cci.pcci_line_size; if (line_size > max) max = line_size; - if (cache_size < cci.pcci_cache_size) - cache_size = cci.pcci_cache_size; if (!cci.pcci_unified) { status = ia64_pal_cache_config_info(l, /* cache_type (instruction)= */ 1, @@ -853,9 +850,6 @@ get_max_cacheline_size (void) ia64_i_cache_stride_shift = cci.pcci_stride; } out: -#ifdef CONFIG_SMP - max_cache_size = max(max_cache_size, cache_size); -#endif if (max > ia64_max_cacheline_size) ia64_max_cacheline_size = max; } diff --git a/arch/mips/kernel/smp.c b/arch/mips/kernel/smp.c index 67edfa7ed93a..a1b017f2dbb3 100644 --- a/arch/mips/kernel/smp.c +++ b/arch/mips/kernel/smp.c @@ -51,16 +51,6 @@ int __cpu_logical_map[NR_CPUS]; /* Map logical to physical */ EXPORT_SYMBOL(phys_cpu_present_map); EXPORT_SYMBOL(cpu_online_map); -/* This happens early in bootup, can't really do it better */ -static void smp_tune_scheduling (void) -{ - struct cache_desc *cd = ¤t_cpu_data.scache; - unsigned long cachesize = cd->linesz * cd->sets * cd->ways; - - if (cachesize > max_cache_size) - max_cache_size = cachesize; -} - extern void __init calibrate_delay(void); extern ATTRIB_NORET void cpu_idle(void); @@ -228,7 +218,6 @@ void __init smp_prepare_cpus(unsigned int max_cpus) { init_new_context(current, &init_mm); current_thread_info()->cpu = 0; - smp_tune_scheduling(); plat_prepare_cpus(max_cpus); #ifndef CONFIG_HOTPLUG_CPU cpu_present_map = cpu_possible_map; diff --git a/arch/sparc/kernel/smp.c b/arch/sparc/kernel/smp.c index 4d9ad59031bb..4fea3ac7bff0 100644 --- a/arch/sparc/kernel/smp.c +++ b/arch/sparc/kernel/smp.c @@ -68,16 +68,6 @@ void __cpuinit smp_store_cpu_info(int id) cpu_data(id).prom_node = cpu_node; cpu_data(id).mid = cpu_get_hwmid(cpu_node); - /* this is required to tune the scheduler correctly */ - /* is it possible to have CPUs with different cache sizes? */ - if (id == boot_cpu_id) { - int cache_line,cache_nlines; - cache_line = 0x20; - cache_line = prom_getintdefault(cpu_node, "ecache-line-size", cache_line); - cache_nlines = 0x8000; - cache_nlines = prom_getintdefault(cpu_node, "ecache-nlines", cache_nlines); - max_cache_size = cache_line * cache_nlines; - } if (cpu_data(id).mid < 0) panic("No MID found for CPU%d at node 0x%08d", id, cpu_node); } diff --git a/arch/sparc64/kernel/smp.c b/arch/sparc64/kernel/smp.c index 4dcd7d0b60f2..40e40f968d61 100644 --- a/arch/sparc64/kernel/smp.c +++ b/arch/sparc64/kernel/smp.c @@ -1163,32 +1163,6 @@ int setup_profiling_timer(unsigned int multiplier) return -EINVAL; } -static void __init smp_tune_scheduling(void) -{ - unsigned int smallest = ~0U; - int i; - - for (i = 0; i < NR_CPUS; i++) { - unsigned int val = cpu_data(i).ecache_size; - - if (val && val < smallest) - smallest = val; - } - - /* Any value less than 256K is nonsense. */ - if (smallest < (256U * 1024U)) - smallest = 256 * 1024; - - max_cache_size = smallest; - - if (smallest < 1U * 1024U * 1024U) - printk(KERN_INFO "Using max_cache_size of %uKB\n", - smallest / 1024U); - else - printk(KERN_INFO "Using max_cache_size of %uMB\n", - smallest / 1024U / 1024U); -} - /* Constrain the number of cpus to max_cpus. */ void __init smp_prepare_cpus(unsigned int max_cpus) { @@ -1206,7 +1180,6 @@ void __init smp_prepare_cpus(unsigned int max_cpus) } cpu_data(boot_cpu_id).udelay_val = loops_per_jiffy; - smp_tune_scheduling(); } void __devinit smp_prepare_boot_cpu(void) diff --git a/include/linux/sched.h b/include/linux/sched.h index 7e74262f98e1..8764cda0feca 100644 --- a/include/linux/sched.h +++ b/include/linux/sched.h @@ -754,12 +754,6 @@ struct sched_domain { extern int partition_sched_domains(cpumask_t *partition1, cpumask_t *partition2); -/* - * Maximum cache size the migration-costs auto-tuning code will - * search from: - */ -extern unsigned int max_cache_size; - #endif /* CONFIG_SMP */ diff --git a/kernel/sched.c b/kernel/sched.c index ac054d9a0719..46b23f0fee24 100644 --- a/kernel/sched.c +++ b/kernel/sched.c @@ -5797,483 +5797,6 @@ init_sched_build_groups(cpumask_t span, const cpumask_t *cpu_map, #define SD_NODES_PER_DOMAIN 16 -/* - * Self-tuning task migration cost measurement between source and target CPUs. - * - * This is done by measuring the cost of manipulating buffers of varying - * sizes. For a given buffer-size here are the steps that are taken: - * - * 1) the source CPU reads+dirties a shared buffer - * 2) the target CPU reads+dirties the same shared buffer - * - * We measure how long they take, in the following 4 scenarios: - * - * - source: CPU1, target: CPU2 | cost1 - * - source: CPU2, target: CPU1 | cost2 - * - source: CPU1, target: CPU1 | cost3 - * - source: CPU2, target: CPU2 | cost4 - * - * We then calculate the cost3+cost4-cost1-cost2 difference - this is - * the cost of migration. - * - * We then start off from a small buffer-size and iterate up to larger - * buffer sizes, in 5% steps - measuring each buffer-size separately, and - * doing a maximum search for the cost. (The maximum cost for a migration - * normally occurs when the working set size is around the effective cache - * size.) - */ -#define SEARCH_SCOPE 2 -#define MIN_CACHE_SIZE (64*1024U) -#define DEFAULT_CACHE_SIZE (5*1024*1024U) -#define ITERATIONS 1 -#define SIZE_THRESH 130 -#define COST_THRESH 130 - -/* - * The migration cost is a function of 'domain distance'. Domain - * distance is the number of steps a CPU has to iterate down its - * domain tree to share a domain with the other CPU. The farther - * two CPUs are from each other, the larger the distance gets. - * - * Note that we use the distance only to cache measurement results, - * the distance value is not used numerically otherwise. When two - * CPUs have the same distance it is assumed that the migration - * cost is the same. (this is a simplification but quite practical) - */ -#define MAX_DOMAIN_DISTANCE 32 - -static unsigned long long migration_cost[MAX_DOMAIN_DISTANCE] = - { [ 0 ... MAX_DOMAIN_DISTANCE-1 ] = -/* - * Architectures may override the migration cost and thus avoid - * boot-time calibration. Unit is nanoseconds. Mostly useful for - * virtualized hardware: - */ -#ifdef CONFIG_DEFAULT_MIGRATION_COST - CONFIG_DEFAULT_MIGRATION_COST -#else - -1LL -#endif -}; - -/* - * Allow override of migration cost - in units of microseconds. - * E.g. migration_cost=1000,2000,3000 will set up a level-1 cost - * of 1 msec, level-2 cost of 2 msecs and level3 cost of 3 msecs: - */ -static int __init migration_cost_setup(char *str) -{ - int ints[MAX_DOMAIN_DISTANCE+1], i; - - str = get_options(str, ARRAY_SIZE(ints), ints); - - printk("#ints: %d\n", ints[0]); - for (i = 1; i <= ints[0]; i++) { - migration_cost[i-1] = (unsigned long long)ints[i]*1000; - printk("migration_cost[%d]: %Ld\n", i-1, migration_cost[i-1]); - } - return 1; -} - -__setup ("migration_cost=", migration_cost_setup); - -/* - * Global multiplier (divisor) for migration-cutoff values, - * in percentiles. E.g. use a value of 150 to get 1.5 times - * longer cache-hot cutoff times. - * - * (We scale it from 100 to 128 to long long handling easier.) - */ - -#define MIGRATION_FACTOR_SCALE 128 - -static unsigned int migration_factor = MIGRATION_FACTOR_SCALE; - -static int __init setup_migration_factor(char *str) -{ - get_option(&str, &migration_factor); - migration_factor = migration_factor * MIGRATION_FACTOR_SCALE / 100; - return 1; -} - -__setup("migration_factor=", setup_migration_factor); - -/* - * Estimated distance of two CPUs, measured via the number of domains - * we have to pass for the two CPUs to be in the same span: - */ -static unsigned long domain_distance(int cpu1, int cpu2) -{ - unsigned long distance = 0; - struct sched_domain *sd; - - for_each_domain(cpu1, sd) { - WARN_ON(!cpu_isset(cpu1, sd->span)); - if (cpu_isset(cpu2, sd->span)) - return distance; - distance++; - } - if (distance >= MAX_DOMAIN_DISTANCE) { - WARN_ON(1); - distance = MAX_DOMAIN_DISTANCE-1; - } - - return distance; -} - -static unsigned int migration_debug; - -static int __init setup_migration_debug(char *str) -{ - get_option(&str, &migration_debug); - return 1; -} - -__setup("migration_debug=", setup_migration_debug); - -/* - * Maximum cache-size that the scheduler should try to measure. - * Architectures with larger caches should tune this up during - * bootup. Gets used in the domain-setup code (i.e. during SMP - * bootup). - */ -unsigned int max_cache_size; - -static int __init setup_max_cache_size(char *str) -{ - get_option(&str, &max_cache_size); - return 1; -} - -__setup("max_cache_size=", setup_max_cache_size); - -/* - * Dirty a big buffer in a hard-to-predict (for the L2 cache) way. This - * is the operation that is timed, so we try to generate unpredictable - * cachemisses that still end up filling the L2 cache: - */ -static void touch_cache(void *__cache, unsigned long __size) -{ - unsigned long size = __size / sizeof(long); - unsigned long chunk1 = size / 3; - unsigned long chunk2 = 2 * size / 3; - unsigned long *cache = __cache; - int i; - - for (i = 0; i < size/6; i += 8) { - switch (i % 6) { - case 0: cache[i]++; - case 1: cache[size-1-i]++; - case 2: cache[chunk1-i]++; - case 3: cache[chunk1+i]++; - case 4: cache[chunk2-i]++; - case 5: cache[chunk2+i]++; - } - } -} - -/* - * Measure the cache-cost of one task migration. Returns in units of nsec. - */ -static unsigned long long -measure_one(void *cache, unsigned long size, int source, int target) -{ - cpumask_t mask, saved_mask; - unsigned long long t0, t1, t2, t3, cost; - - saved_mask = current->cpus_allowed; - - /* - * Flush source caches to RAM and invalidate them: - */ - sched_cacheflush(); - - /* - * Migrate to the source CPU: - */ - mask = cpumask_of_cpu(source); - set_cpus_allowed(current, mask); - WARN_ON(smp_processor_id() != source); - - /* - * Dirty the working set: - */ - t0 = sched_clock(); - touch_cache(cache, size); - t1 = sched_clock(); - - /* - * Migrate to the target CPU, dirty the L2 cache and access - * the shared buffer. (which represents the working set - * of a migrated task.) - */ - mask = cpumask_of_cpu(target); - set_cpus_allowed(current, mask); - WARN_ON(smp_processor_id() != target); - - t2 = sched_clock(); - touch_cache(cache, size); - t3 = sched_clock(); - - cost = t1-t0 + t3-t2; - - if (migration_debug >= 2) - printk("[%d->%d]: %8Ld %8Ld %8Ld => %10Ld.\n", - source, target, t1-t0, t1-t0, t3-t2, cost); - /* - * Flush target caches to RAM and invalidate them: - */ - sched_cacheflush(); - - set_cpus_allowed(current, saved_mask); - - return cost; -} - -/* - * Measure a series of task migrations and return the average - * result. Since this code runs early during bootup the system - * is 'undisturbed' and the average latency makes sense. - * - * The algorithm in essence auto-detects the relevant cache-size, - * so it will properly detect different cachesizes for different - * cache-hierarchies, depending on how the CPUs are connected. - * - * Architectures can prime the upper limit of the search range via - * max_cache_size, otherwise the search range defaults to 20MB...64K. - */ -static unsigned long long -measure_cost(int cpu1, int cpu2, void *cache, unsigned int size) -{ - unsigned long long cost1, cost2; - int i; - - /* - * Measure the migration cost of 'size' bytes, over an - * average of 10 runs: - * - * (We perturb the cache size by a small (0..4k) - * value to compensate size/alignment related artifacts. - * We also subtract the cost of the operation done on - * the same CPU.) - */ - cost1 = 0; - - /* - * dry run, to make sure we start off cache-cold on cpu1, - * and to get any vmalloc pagefaults in advance: - */ - measure_one(cache, size, cpu1, cpu2); - for (i = 0; i < ITERATIONS; i++) - cost1 += measure_one(cache, size - i * 1024, cpu1, cpu2); - - measure_one(cache, size, cpu2, cpu1); - for (i = 0; i < ITERATIONS; i++) - cost1 += measure_one(cache, size - i * 1024, cpu2, cpu1); - - /* - * (We measure the non-migrating [cached] cost on both - * cpu1 and cpu2, to handle CPUs with different speeds) - */ - cost2 = 0; - - measure_one(cache, size, cpu1, cpu1); - for (i = 0; i < ITERATIONS; i++) - cost2 += measure_one(cache, size - i * 1024, cpu1, cpu1); - - measure_one(cache, size, cpu2, cpu2); - for (i = 0; i < ITERATIONS; i++) - cost2 += measure_one(cache, size - i * 1024, cpu2, cpu2); - - /* - * Get the per-iteration migration cost: - */ - do_div(cost1, 2 * ITERATIONS); - do_div(cost2, 2 * ITERATIONS); - - return cost1 - cost2; -} - -static unsigned long long measure_migration_cost(int cpu1, int cpu2) -{ - unsigned long long max_cost = 0, fluct = 0, avg_fluct = 0; - unsigned int max_size, size, size_found = 0; - long long cost = 0, prev_cost; - void *cache; - - /* - * Search from max_cache_size*5 down to 64K - the real relevant - * cachesize has to lie somewhere inbetween. - */ - if (max_cache_size) { - max_size = max(max_cache_size * SEARCH_SCOPE, MIN_CACHE_SIZE); - size = max(max_cache_size / SEARCH_SCOPE, MIN_CACHE_SIZE); - } else { - /* - * Since we have no estimation about the relevant - * search range - */ - max_size = DEFAULT_CACHE_SIZE * SEARCH_SCOPE; - size = MIN_CACHE_SIZE; - } - - if (!cpu_online(cpu1) || !cpu_online(cpu2)) { - printk("cpu %d and %d not both online!\n", cpu1, cpu2); - return 0; - } - - /* - * Allocate the working set: - */ - cache = vmalloc(max_size); - if (!cache) { - printk("could not vmalloc %d bytes for cache!\n", 2 * max_size); - return 1000000; /* return 1 msec on very small boxen */ - } - - while (size <= max_size) { - prev_cost = cost; - cost = measure_cost(cpu1, cpu2, cache, size); - - /* - * Update the max: - */ - if (cost > 0) { - if (max_cost < cost) { - max_cost = cost; - size_found = size; - } - } - /* - * Calculate average fluctuation, we use this to prevent - * noise from triggering an early break out of the loop: - */ - fluct = abs(cost - prev_cost); - avg_fluct = (avg_fluct + fluct)/2; - - if (migration_debug) - printk("-> [%d][%d][%7d] %3ld.%ld [%3ld.%ld] (%ld): " - "(%8Ld %8Ld)\n", - cpu1, cpu2, size, - (long)cost / 1000000, - ((long)cost / 100000) % 10, - (long)max_cost / 1000000, - ((long)max_cost / 100000) % 10, - domain_distance(cpu1, cpu2), - cost, avg_fluct); - - /* - * If we iterated at least 20% past the previous maximum, - * and the cost has dropped by more than 20% already, - * (taking fluctuations into account) then we assume to - * have found the maximum and break out of the loop early: - */ - if (size_found && (size*100 > size_found*SIZE_THRESH)) - if (cost+avg_fluct <= 0 || - max_cost*100 > (cost+avg_fluct)*COST_THRESH) { - - if (migration_debug) - printk("-> found max.\n"); - break; - } - /* - * Increase the cachesize in 10% steps: - */ - size = size * 10 / 9; - } - - if (migration_debug) - printk("[%d][%d] working set size found: %d, cost: %Ld\n", - cpu1, cpu2, size_found, max_cost); - - vfree(cache); - - /* - * A task is considered 'cache cold' if at least 2 times - * the worst-case cost of migration has passed. - * - * (this limit is only listened to if the load-balancing - * situation is 'nice' - if there is a large imbalance we - * ignore it for the sake of CPU utilization and - * processing fairness.) - */ - return 2 * max_cost * migration_factor / MIGRATION_FACTOR_SCALE; -} - -static void calibrate_migration_costs(const cpumask_t *cpu_map) -{ - int cpu1 = -1, cpu2 = -1, cpu, orig_cpu = raw_smp_processor_id(); - unsigned long j0, j1, distance, max_distance = 0; - struct sched_domain *sd; - - j0 = jiffies; - - /* - * First pass - calculate the cacheflush times: - */ - for_each_cpu_mask(cpu1, *cpu_map) { - for_each_cpu_mask(cpu2, *cpu_map) { - if (cpu1 == cpu2) - continue; - distance = domain_distance(cpu1, cpu2); - max_distance = max(max_distance, distance); - /* - * No result cached yet? - */ - if (migration_cost[distance] == -1LL) - migration_cost[distance] = - measure_migration_cost(cpu1, cpu2); - } - } - /* - * Second pass - update the sched domain hierarchy with - * the new cache-hot-time estimations: - */ - for_each_cpu_mask(cpu, *cpu_map) { - distance = 0; - for_each_domain(cpu, sd) { - sd->cache_hot_time = migration_cost[distance]; - distance++; - } - } - /* - * Print the matrix: - */ - if (migration_debug) - printk("migration: max_cache_size: %d, cpu: %d MHz:\n", - max_cache_size, -#ifdef CONFIG_X86 - cpu_khz/1000 -#else - -1 -#endif - ); - if (system_state == SYSTEM_BOOTING && num_online_cpus() > 1) { - printk("migration_cost="); - for (distance = 0; distance <= max_distance; distance++) { - if (distance) - printk(","); - printk("%ld", (long)migration_cost[distance] / 1000); - } - printk("\n"); - } - j1 = jiffies; - if (migration_debug) - printk("migration: %ld seconds\n", (j1-j0) / HZ); - - /* - * Move back to the original CPU. NUMA-Q gets confused - * if we migrate to another quad during bootup. - */ - if (raw_smp_processor_id() != orig_cpu) { - cpumask_t mask = cpumask_of_cpu(orig_cpu), - saved_mask = current->cpus_allowed; - - set_cpus_allowed(current, mask); - set_cpus_allowed(current, saved_mask); - } -} - #ifdef CONFIG_NUMA /** @@ -6803,10 +6326,6 @@ static int build_sched_domains(const cpumask_t *cpu_map) #endif cpu_attach_domain(sd, i); } - /* - * Tune cache-hot values: - */ - calibrate_migration_costs(cpu_map); return 0; -- cgit v1.2.3 From c65cc8705256ad7524c97564b4fe3ca9782bf6d1 Mon Sep 17 00:00:00 2001 From: Ingo Molnar Date: Mon, 9 Jul 2007 18:51:58 +0200 Subject: sched: uninline set_task_cpu() uninline set_task_cpu(): CFS will add more code to it. Signed-off-by: Ingo Molnar --- include/linux/sched.h | 5 +---- kernel/sched.c | 6 ++++++ 2 files changed, 7 insertions(+), 4 deletions(-) (limited to 'include/linux/sched.h') diff --git a/include/linux/sched.h b/include/linux/sched.h index 8764cda0feca..4b912e753ca0 100644 --- a/include/linux/sched.h +++ b/include/linux/sched.h @@ -1633,10 +1633,7 @@ static inline unsigned int task_cpu(const struct task_struct *p) return task_thread_info(p)->cpu; } -static inline void set_task_cpu(struct task_struct *p, unsigned int cpu) -{ - task_thread_info(p)->cpu = cpu; -} +extern void set_task_cpu(struct task_struct *p, unsigned int cpu); #else diff --git a/kernel/sched.c b/kernel/sched.c index 46b23f0fee24..d6624978feb2 100644 --- a/kernel/sched.c +++ b/kernel/sched.c @@ -1111,6 +1111,12 @@ unsigned long weighted_cpuload(const int cpu) } #ifdef CONFIG_SMP + +void set_task_cpu(struct task_struct *p, unsigned int cpu) +{ + task_thread_info(p)->cpu = cpu; +} + struct migration_req { struct list_head list; -- cgit v1.2.3 From 1df21055e34b6a68d62cf0c524b9e52deebd7ead Mon Sep 17 00:00:00 2001 From: Ingo Molnar Date: Mon, 9 Jul 2007 18:51:58 +0200 Subject: sched: add init_idle_bootup_task() add the init_idle_bootup_task() callback to the bootup thread, unused at the moment. (CFS will use it to switch the scheduling class of the boot thread to the idle class) Signed-off-by: Ingo Molnar --- include/linux/sched.h | 1 + init/main.c | 5 +++-- kernel/sched.c | 5 +++++ 3 files changed, 9 insertions(+), 2 deletions(-) (limited to 'include/linux/sched.h') diff --git a/include/linux/sched.h b/include/linux/sched.h index 4b912e753ca0..61a111fe2b7a 100644 --- a/include/linux/sched.h +++ b/include/linux/sched.h @@ -195,6 +195,7 @@ struct task_struct; extern void sched_init(void); extern void sched_init_smp(void); extern void init_idle(struct task_struct *idle, int cpu); +extern void init_idle_bootup_task(struct task_struct *idle); extern cpumask_t nohz_cpu_mask; #if defined(CONFIG_SMP) && defined(CONFIG_NO_HZ) diff --git a/init/main.c b/init/main.c index eb8bdbae4fc7..0eb1c7463fe4 100644 --- a/init/main.c +++ b/init/main.c @@ -436,15 +436,16 @@ static void noinline __init_refok rest_init(void) /* * The boot idle thread must execute schedule() - * at least one to get things moving: + * at least once to get things moving: */ + init_idle_bootup_task(current); preempt_enable_no_resched(); schedule(); preempt_disable(); /* Call into cpu_idle with preempt disabled */ cpu_idle(); -} +} /* Check for early params. */ static int __init do_early_param(char *param, char *val) diff --git a/kernel/sched.c b/kernel/sched.c index 7090982350d3..ac4d26241d1e 100644 --- a/kernel/sched.c +++ b/kernel/sched.c @@ -5018,6 +5018,11 @@ void show_state_filter(unsigned long state_filter) debug_show_all_locks(); } +void __cpuinit init_idle_bootup_task(struct task_struct *idle) +{ + /* nothing yet */ +} + /** * init_idle - set up an idle thread for a given CPU * @idle: task in question -- cgit v1.2.3 From 9aa7b369819940cb1f3c74ba210516739a32ad95 Mon Sep 17 00:00:00 2001 From: Ingo Molnar Date: Mon, 9 Jul 2007 18:51:58 +0200 Subject: sched: increase the resolution of smpnice increase SMP-nice's resolution. This is needed by CFS to implement SCHED_IDLE and cleaned up nice level support. no behavioral changes. Signed-off-by: Ingo Molnar --- include/linux/sched.h | 9 ++++++++- 1 file changed, 8 insertions(+), 1 deletion(-) (limited to 'include/linux/sched.h') diff --git a/include/linux/sched.h b/include/linux/sched.h index 61a111fe2b7a..d5084e7c48cf 100644 --- a/include/linux/sched.h +++ b/include/linux/sched.h @@ -652,7 +652,14 @@ enum cpu_idle_type { /* * sched-domains (multiprocessor balancing) declarations: */ -#define SCHED_LOAD_SCALE 128UL /* increase resolution of load */ + +/* + * Increase resolution of nice-level calculations: + */ +#define SCHED_LOAD_SHIFT 10 +#define SCHED_LOAD_SCALE (1L << SCHED_LOAD_SHIFT) + +#define SCHED_LOAD_SCALE_FUZZ (SCHED_LOAD_SCALE >> 5) #ifdef CONFIG_SMP #define SD_LOAD_BALANCE 1 /* Do load balancing on this domain. */ -- cgit v1.2.3 From bf0f6f24a1ece8988b243aefe84ee613099a9245 Mon Sep 17 00:00:00 2001 From: Ingo Molnar Date: Mon, 9 Jul 2007 18:51:58 +0200 Subject: sched: cfs core, kernel/sched_fair.c add kernel/sched_fair.c - which implements the bulk of CFS's behavioral changes for SCHED_OTHER tasks. see Documentation/sched-design-CFS.txt about details. Authors: Ingo Molnar Dmitry Adamushko Srivatsa Vaddagiri Mike Galbraith Signed-off-by: Ingo Molnar Signed-off-by: Mike Galbraith Signed-off-by: Dmitry Adamushko Signed-off-by: Srivatsa Vaddagiri --- include/linux/sched.h | 8 + kernel/sched_fair.c | 1131 +++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 1139 insertions(+) create mode 100644 kernel/sched_fair.c (limited to 'include/linux/sched.h') diff --git a/include/linux/sched.h b/include/linux/sched.h index d5084e7c48cf..90420321994f 100644 --- a/include/linux/sched.h +++ b/include/linux/sched.h @@ -1243,6 +1243,14 @@ static inline void idle_task_exit(void) {} extern void sched_idle_next(void); +extern unsigned int sysctl_sched_granularity; +extern unsigned int sysctl_sched_wakeup_granularity; +extern unsigned int sysctl_sched_batch_wakeup_granularity; +extern unsigned int sysctl_sched_stat_granularity; +extern unsigned int sysctl_sched_runtime_limit; +extern unsigned int sysctl_sched_child_runs_first; +extern unsigned int sysctl_sched_features; + #ifdef CONFIG_RT_MUTEXES extern int rt_mutex_getprio(struct task_struct *p); extern void rt_mutex_setprio(struct task_struct *p, int prio); diff --git a/kernel/sched_fair.c b/kernel/sched_fair.c new file mode 100644 index 000000000000..6971db0a7160 --- /dev/null +++ b/kernel/sched_fair.c @@ -0,0 +1,1131 @@ +/* + * Completely Fair Scheduling (CFS) Class (SCHED_NORMAL/SCHED_BATCH) + * + * Copyright (C) 2007 Red Hat, Inc., Ingo Molnar + * + * Interactivity improvements by Mike Galbraith + * (C) 2007 Mike Galbraith + * + * Various enhancements by Dmitry Adamushko. + * (C) 2007 Dmitry Adamushko + * + * Group scheduling enhancements by Srivatsa Vaddagiri + * Copyright IBM Corporation, 2007 + * Author: Srivatsa Vaddagiri + * + * Scaled math optimizations by Thomas Gleixner + * Copyright (C) 2007, Thomas Gleixner + */ + +/* + * Preemption granularity: + * (default: 2 msec, units: nanoseconds) + * + * NOTE: this granularity value is not the same as the concept of + * 'timeslice length' - timeslices in CFS will typically be somewhat + * larger than this value. (to see the precise effective timeslice + * length of your workload, run vmstat and monitor the context-switches + * field) + * + * On SMP systems the value of this is multiplied by the log2 of the + * number of CPUs. (i.e. factor 2x on 2-way systems, 3x on 4-way + * systems, 4x on 8-way systems, 5x on 16-way systems, etc.) + */ +unsigned int sysctl_sched_granularity __read_mostly = 2000000000ULL/HZ; + +/* + * SCHED_BATCH wake-up granularity. + * (default: 10 msec, units: nanoseconds) + * + * This option delays the preemption effects of decoupled workloads + * and reduces their over-scheduling. Synchronous workloads will still + * have immediate wakeup/sleep latencies. + */ +unsigned int sysctl_sched_batch_wakeup_granularity __read_mostly = + 10000000000ULL/HZ; + +/* + * SCHED_OTHER wake-up granularity. + * (default: 1 msec, units: nanoseconds) + * + * This option delays the preemption effects of decoupled workloads + * and reduces their over-scheduling. Synchronous workloads will still + * have immediate wakeup/sleep latencies. + */ +unsigned int sysctl_sched_wakeup_granularity __read_mostly = 1000000000ULL/HZ; + +unsigned int sysctl_sched_stat_granularity __read_mostly; + +/* + * Initialized in sched_init_granularity(): + */ +unsigned int sysctl_sched_runtime_limit __read_mostly; + +/* + * Debugging: various feature bits + */ +enum { + SCHED_FEAT_FAIR_SLEEPERS = 1, + SCHED_FEAT_SLEEPER_AVG = 2, + SCHED_FEAT_SLEEPER_LOAD_AVG = 4, + SCHED_FEAT_PRECISE_CPU_LOAD = 8, + SCHED_FEAT_START_DEBIT = 16, + SCHED_FEAT_SKIP_INITIAL = 32, +}; + +unsigned int sysctl_sched_features __read_mostly = + SCHED_FEAT_FAIR_SLEEPERS *1 | + SCHED_FEAT_SLEEPER_AVG *1 | + SCHED_FEAT_SLEEPER_LOAD_AVG *1 | + SCHED_FEAT_PRECISE_CPU_LOAD *1 | + SCHED_FEAT_START_DEBIT *1 | + SCHED_FEAT_SKIP_INITIAL *0; + +extern struct sched_class fair_sched_class; + +/************************************************************** + * CFS operations on generic schedulable entities: + */ + +#ifdef CONFIG_FAIR_GROUP_SCHED + +/* cpu runqueue to which this cfs_rq is attached */ +static inline struct rq *rq_of(struct cfs_rq *cfs_rq) +{ + return cfs_rq->rq; +} + +/* currently running entity (if any) on this cfs_rq */ +static inline struct sched_entity *cfs_rq_curr(struct cfs_rq *cfs_rq) +{ + return cfs_rq->curr; +} + +/* An entity is a task if it doesn't "own" a runqueue */ +#define entity_is_task(se) (!se->my_q) + +static inline void +set_cfs_rq_curr(struct cfs_rq *cfs_rq, struct sched_entity *se) +{ + cfs_rq->curr = se; +} + +#else /* CONFIG_FAIR_GROUP_SCHED */ + +static inline struct rq *rq_of(struct cfs_rq *cfs_rq) +{ + return container_of(cfs_rq, struct rq, cfs); +} + +static inline struct sched_entity *cfs_rq_curr(struct cfs_rq *cfs_rq) +{ + struct rq *rq = rq_of(cfs_rq); + + if (unlikely(rq->curr->sched_class != &fair_sched_class)) + return NULL; + + return &rq->curr->se; +} + +#define entity_is_task(se) 1 + +static inline void +set_cfs_rq_curr(struct cfs_rq *cfs_rq, struct sched_entity *se) { } + +#endif /* CONFIG_FAIR_GROUP_SCHED */ + +static inline struct task_struct *task_of(struct sched_entity *se) +{ + return container_of(se, struct task_struct, se); +} + + +/************************************************************** + * Scheduling class tree data structure manipulation methods: + */ + +/* + * Enqueue an entity into the rb-tree: + */ +static inline void +__enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se) +{ + struct rb_node **link = &cfs_rq->tasks_timeline.rb_node; + struct rb_node *parent = NULL; + struct sched_entity *entry; + s64 key = se->fair_key; + int leftmost = 1; + + /* + * Find the right place in the rbtree: + */ + while (*link) { + parent = *link; + entry = rb_entry(parent, struct sched_entity, run_node); + /* + * We dont care about collisions. Nodes with + * the same key stay together. + */ + if (key - entry->fair_key < 0) { + link = &parent->rb_left; + } else { + link = &parent->rb_right; + leftmost = 0; + } + } + + /* + * Maintain a cache of leftmost tree entries (it is frequently + * used): + */ + if (leftmost) + cfs_rq->rb_leftmost = &se->run_node; + + rb_link_node(&se->run_node, parent, link); + rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline); + update_load_add(&cfs_rq->load, se->load.weight); + cfs_rq->nr_running++; + se->on_rq = 1; +} + +static inline void +__dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se) +{ + if (cfs_rq->rb_leftmost == &se->run_node) + cfs_rq->rb_leftmost = rb_next(&se->run_node); + rb_erase(&se->run_node, &cfs_rq->tasks_timeline); + update_load_sub(&cfs_rq->load, se->load.weight); + cfs_rq->nr_running--; + se->on_rq = 0; +} + +static inline struct rb_node *first_fair(struct cfs_rq *cfs_rq) +{ + return cfs_rq->rb_leftmost; +} + +static struct sched_entity *__pick_next_entity(struct cfs_rq *cfs_rq) +{ + return rb_entry(first_fair(cfs_rq), struct sched_entity, run_node); +} + +/************************************************************** + * Scheduling class statistics methods: + */ + +/* + * We rescale the rescheduling granularity of tasks according to their + * nice level, but only linearly, not exponentially: + */ +static long +niced_granularity(struct sched_entity *curr, unsigned long granularity) +{ + u64 tmp; + + /* + * Negative nice levels get the same granularity as nice-0: + */ + if (likely(curr->load.weight >= NICE_0_LOAD)) + return granularity; + /* + * Positive nice level tasks get linearly finer + * granularity: + */ + tmp = curr->load.weight * (u64)granularity; + + /* + * It will always fit into 'long': + */ + return (long) (tmp >> NICE_0_SHIFT); +} + +static inline void +limit_wait_runtime(struct cfs_rq *cfs_rq, struct sched_entity *se) +{ + long limit = sysctl_sched_runtime_limit; + + /* + * Niced tasks have the same history dynamic range as + * non-niced tasks: + */ + if (unlikely(se->wait_runtime > limit)) { + se->wait_runtime = limit; + schedstat_inc(se, wait_runtime_overruns); + schedstat_inc(cfs_rq, wait_runtime_overruns); + } + if (unlikely(se->wait_runtime < -limit)) { + se->wait_runtime = -limit; + schedstat_inc(se, wait_runtime_underruns); + schedstat_inc(cfs_rq, wait_runtime_underruns); + } +} + +static inline void +__add_wait_runtime(struct cfs_rq *cfs_rq, struct sched_entity *se, long delta) +{ + se->wait_runtime += delta; + schedstat_add(se, sum_wait_runtime, delta); + limit_wait_runtime(cfs_rq, se); +} + +static void +add_wait_runtime(struct cfs_rq *cfs_rq, struct sched_entity *se, long delta) +{ + schedstat_add(cfs_rq, wait_runtime, -se->wait_runtime); + __add_wait_runtime(cfs_rq, se, delta); + schedstat_add(cfs_rq, wait_runtime, se->wait_runtime); +} + +/* + * Update the current task's runtime statistics. Skip current tasks that + * are not in our scheduling class. + */ +static inline void +__update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr, u64 now) +{ + unsigned long delta, delta_exec, delta_fair; + long delta_mine; + struct load_weight *lw = &cfs_rq->load; + unsigned long load = lw->weight; + + if (unlikely(!load)) + return; + + delta_exec = curr->delta_exec; +#ifdef CONFIG_SCHEDSTATS + if (unlikely(delta_exec > curr->exec_max)) + curr->exec_max = delta_exec; +#endif + + curr->sum_exec_runtime += delta_exec; + cfs_rq->exec_clock += delta_exec; + + delta_fair = calc_delta_fair(delta_exec, lw); + delta_mine = calc_delta_mine(delta_exec, curr->load.weight, lw); + + if (cfs_rq->sleeper_bonus > sysctl_sched_stat_granularity) { + delta = calc_delta_mine(cfs_rq->sleeper_bonus, + curr->load.weight, lw); + if (unlikely(delta > cfs_rq->sleeper_bonus)) + delta = cfs_rq->sleeper_bonus; + + cfs_rq->sleeper_bonus -= delta; + delta_mine -= delta; + } + + cfs_rq->fair_clock += delta_fair; + /* + * We executed delta_exec amount of time on the CPU, + * but we were only entitled to delta_mine amount of + * time during that period (if nr_running == 1 then + * the two values are equal) + * [Note: delta_mine - delta_exec is negative]: + */ + add_wait_runtime(cfs_rq, curr, delta_mine - delta_exec); +} + +static void update_curr(struct cfs_rq *cfs_rq, u64 now) +{ + struct sched_entity *curr = cfs_rq_curr(cfs_rq); + unsigned long delta_exec; + + if (unlikely(!curr)) + return; + + /* + * Get the amount of time the current task was running + * since the last time we changed load (this cannot + * overflow on 32 bits): + */ + delta_exec = (unsigned long)(now - curr->exec_start); + + curr->delta_exec += delta_exec; + + if (unlikely(curr->delta_exec > sysctl_sched_stat_granularity)) { + __update_curr(cfs_rq, curr, now); + curr->delta_exec = 0; + } + curr->exec_start = now; +} + +static inline void +update_stats_wait_start(struct cfs_rq *cfs_rq, struct sched_entity *se, u64 now) +{ + se->wait_start_fair = cfs_rq->fair_clock; + se->wait_start = now; +} + +/* + * We calculate fair deltas here, so protect against the random effects + * of a multiplication overflow by capping it to the runtime limit: + */ +#if BITS_PER_LONG == 32 +static inline unsigned long +calc_weighted(unsigned long delta, unsigned long weight, int shift) +{ + u64 tmp = (u64)delta * weight >> shift; + + if (unlikely(tmp > sysctl_sched_runtime_limit*2)) + return sysctl_sched_runtime_limit*2; + return tmp; +} +#else +static inline unsigned long +calc_weighted(unsigned long delta, unsigned long weight, int shift) +{ + return delta * weight >> shift; +} +#endif + +/* + * Task is being enqueued - update stats: + */ +static void +update_stats_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se, u64 now) +{ + s64 key; + + /* + * Are we enqueueing a waiting task? (for current tasks + * a dequeue/enqueue event is a NOP) + */ + if (se != cfs_rq_curr(cfs_rq)) + update_stats_wait_start(cfs_rq, se, now); + /* + * Update the key: + */ + key = cfs_rq->fair_clock; + + /* + * Optimize the common nice 0 case: + */ + if (likely(se->load.weight == NICE_0_LOAD)) { + key -= se->wait_runtime; + } else { + u64 tmp; + + if (se->wait_runtime < 0) { + tmp = -se->wait_runtime; + key += (tmp * se->load.inv_weight) >> + (WMULT_SHIFT - NICE_0_SHIFT); + } else { + tmp = se->wait_runtime; + key -= (tmp * se->load.weight) >> NICE_0_SHIFT; + } + } + + se->fair_key = key; +} + +/* + * Note: must be called with a freshly updated rq->fair_clock. + */ +static inline void +__update_stats_wait_end(struct cfs_rq *cfs_rq, struct sched_entity *se, u64 now) +{ + unsigned long delta_fair = se->delta_fair_run; + +#ifdef CONFIG_SCHEDSTATS + { + s64 delta_wait = now - se->wait_start; + if (unlikely(delta_wait > se->wait_max)) + se->wait_max = delta_wait; + } +#endif + + if (unlikely(se->load.weight != NICE_0_LOAD)) + delta_fair = calc_weighted(delta_fair, se->load.weight, + NICE_0_SHIFT); + + add_wait_runtime(cfs_rq, se, delta_fair); +} + +static void +update_stats_wait_end(struct cfs_rq *cfs_rq, struct sched_entity *se, u64 now) +{ + unsigned long delta_fair; + + delta_fair = (unsigned long)min((u64)(2*sysctl_sched_runtime_limit), + (u64)(cfs_rq->fair_clock - se->wait_start_fair)); + + se->delta_fair_run += delta_fair; + if (unlikely(abs(se->delta_fair_run) >= + sysctl_sched_stat_granularity)) { + __update_stats_wait_end(cfs_rq, se, now); + se->delta_fair_run = 0; + } + + se->wait_start_fair = 0; + se->wait_start = 0; +} + +static inline void +update_stats_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se, u64 now) +{ + update_curr(cfs_rq, now); + /* + * Mark the end of the wait period if dequeueing a + * waiting task: + */ + if (se != cfs_rq_curr(cfs_rq)) + update_stats_wait_end(cfs_rq, se, now); +} + +/* + * We are picking a new current task - update its stats: + */ +static inline void +update_stats_curr_start(struct cfs_rq *cfs_rq, struct sched_entity *se, u64 now) +{ + /* + * We are starting a new run period: + */ + se->exec_start = now; +} + +/* + * We are descheduling a task - update its stats: + */ +static inline void +update_stats_curr_end(struct cfs_rq *cfs_rq, struct sched_entity *se, u64 now) +{ + se->exec_start = 0; +} + +/************************************************** + * Scheduling class queueing methods: + */ + +static void +__enqueue_sleeper(struct cfs_rq *cfs_rq, struct sched_entity *se, u64 now) +{ + unsigned long load = cfs_rq->load.weight, delta_fair; + long prev_runtime; + + if (sysctl_sched_features & SCHED_FEAT_SLEEPER_LOAD_AVG) + load = rq_of(cfs_rq)->cpu_load[2]; + + delta_fair = se->delta_fair_sleep; + + /* + * Fix up delta_fair with the effect of us running + * during the whole sleep period: + */ + if (sysctl_sched_features & SCHED_FEAT_SLEEPER_AVG) + delta_fair = div64_likely32((u64)delta_fair * load, + load + se->load.weight); + + if (unlikely(se->load.weight != NICE_0_LOAD)) + delta_fair = calc_weighted(delta_fair, se->load.weight, + NICE_0_SHIFT); + + prev_runtime = se->wait_runtime; + __add_wait_runtime(cfs_rq, se, delta_fair); + delta_fair = se->wait_runtime - prev_runtime; + + /* + * Track the amount of bonus we've given to sleepers: + */ + cfs_rq->sleeper_bonus += delta_fair; + + schedstat_add(cfs_rq, wait_runtime, se->wait_runtime); +} + +static void +enqueue_sleeper(struct cfs_rq *cfs_rq, struct sched_entity *se, u64 now) +{ + struct task_struct *tsk = task_of(se); + unsigned long delta_fair; + + if ((entity_is_task(se) && tsk->policy == SCHED_BATCH) || + !(sysctl_sched_features & SCHED_FEAT_FAIR_SLEEPERS)) + return; + + delta_fair = (unsigned long)min((u64)(2*sysctl_sched_runtime_limit), + (u64)(cfs_rq->fair_clock - se->sleep_start_fair)); + + se->delta_fair_sleep += delta_fair; + if (unlikely(abs(se->delta_fair_sleep) >= + sysctl_sched_stat_granularity)) { + __enqueue_sleeper(cfs_rq, se, now); + se->delta_fair_sleep = 0; + } + + se->sleep_start_fair = 0; + +#ifdef CONFIG_SCHEDSTATS + if (se->sleep_start) { + u64 delta = now - se->sleep_start; + + if ((s64)delta < 0) + delta = 0; + + if (unlikely(delta > se->sleep_max)) + se->sleep_max = delta; + + se->sleep_start = 0; + se->sum_sleep_runtime += delta; + } + if (se->block_start) { + u64 delta = now - se->block_start; + + if ((s64)delta < 0) + delta = 0; + + if (unlikely(delta > se->block_max)) + se->block_max = delta; + + se->block_start = 0; + se->sum_sleep_runtime += delta; + } +#endif +} + +static void +enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, + int wakeup, u64 now) +{ + /* + * Update the fair clock. + */ + update_curr(cfs_rq, now); + + if (wakeup) + enqueue_sleeper(cfs_rq, se, now); + + update_stats_enqueue(cfs_rq, se, now); + __enqueue_entity(cfs_rq, se); +} + +static void +dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, + int sleep, u64 now) +{ + update_stats_dequeue(cfs_rq, se, now); + if (sleep) { + se->sleep_start_fair = cfs_rq->fair_clock; +#ifdef CONFIG_SCHEDSTATS + if (entity_is_task(se)) { + struct task_struct *tsk = task_of(se); + + if (tsk->state & TASK_INTERRUPTIBLE) + se->sleep_start = now; + if (tsk->state & TASK_UNINTERRUPTIBLE) + se->block_start = now; + } + cfs_rq->wait_runtime -= se->wait_runtime; +#endif + } + __dequeue_entity(cfs_rq, se); +} + +/* + * Preempt the current task with a newly woken task if needed: + */ +static void +__check_preempt_curr_fair(struct cfs_rq *cfs_rq, struct sched_entity *se, + struct sched_entity *curr, unsigned long granularity) +{ + s64 __delta = curr->fair_key - se->fair_key; + + /* + * Take scheduling granularity into account - do not + * preempt the current task unless the best task has + * a larger than sched_granularity fairness advantage: + */ + if (__delta > niced_granularity(curr, granularity)) + resched_task(rq_of(cfs_rq)->curr); +} + +static inline void +set_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, u64 now) +{ + /* + * Any task has to be enqueued before it get to execute on + * a CPU. So account for the time it spent waiting on the + * runqueue. (note, here we rely on pick_next_task() having + * done a put_prev_task_fair() shortly before this, which + * updated rq->fair_clock - used by update_stats_wait_end()) + */ + update_stats_wait_end(cfs_rq, se, now); + update_stats_curr_start(cfs_rq, se, now); + set_cfs_rq_curr(cfs_rq, se); +} + +static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq, u64 now) +{ + struct sched_entity *se = __pick_next_entity(cfs_rq); + + set_next_entity(cfs_rq, se, now); + + return se; +} + +static void +put_prev_entity(struct cfs_rq *cfs_rq, struct sched_entity *prev, u64 now) +{ + /* + * If still on the runqueue then deactivate_task() + * was not called and update_curr() has to be done: + */ + if (prev->on_rq) + update_curr(cfs_rq, now); + + update_stats_curr_end(cfs_rq, prev, now); + + if (prev->on_rq) + update_stats_wait_start(cfs_rq, prev, now); + set_cfs_rq_curr(cfs_rq, NULL); +} + +static void entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr) +{ + struct rq *rq = rq_of(cfs_rq); + struct sched_entity *next; + u64 now = __rq_clock(rq); + + /* + * Dequeue and enqueue the task to update its + * position within the tree: + */ + dequeue_entity(cfs_rq, curr, 0, now); + enqueue_entity(cfs_rq, curr, 0, now); + + /* + * Reschedule if another task tops the current one. + */ + next = __pick_next_entity(cfs_rq); + if (next == curr) + return; + + __check_preempt_curr_fair(cfs_rq, next, curr, sysctl_sched_granularity); +} + +/************************************************** + * CFS operations on tasks: + */ + +#ifdef CONFIG_FAIR_GROUP_SCHED + +/* Walk up scheduling entities hierarchy */ +#define for_each_sched_entity(se) \ + for (; se; se = se->parent) + +static inline struct cfs_rq *task_cfs_rq(struct task_struct *p) +{ + return p->se.cfs_rq; +} + +/* runqueue on which this entity is (to be) queued */ +static inline struct cfs_rq *cfs_rq_of(struct sched_entity *se) +{ + return se->cfs_rq; +} + +/* runqueue "owned" by this group */ +static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp) +{ + return grp->my_q; +} + +/* Given a group's cfs_rq on one cpu, return its corresponding cfs_rq on + * another cpu ('this_cpu') + */ +static inline struct cfs_rq *cpu_cfs_rq(struct cfs_rq *cfs_rq, int this_cpu) +{ + /* A later patch will take group into account */ + return &cpu_rq(this_cpu)->cfs; +} + +/* Iterate thr' all leaf cfs_rq's on a runqueue */ +#define for_each_leaf_cfs_rq(rq, cfs_rq) \ + list_for_each_entry(cfs_rq, &rq->leaf_cfs_rq_list, leaf_cfs_rq_list) + +/* Do the two (enqueued) tasks belong to the same group ? */ +static inline int is_same_group(struct task_struct *curr, struct task_struct *p) +{ + if (curr->se.cfs_rq == p->se.cfs_rq) + return 1; + + return 0; +} + +#else /* CONFIG_FAIR_GROUP_SCHED */ + +#define for_each_sched_entity(se) \ + for (; se; se = NULL) + +static inline struct cfs_rq *task_cfs_rq(struct task_struct *p) +{ + return &task_rq(p)->cfs; +} + +static inline struct cfs_rq *cfs_rq_of(struct sched_entity *se) +{ + struct task_struct *p = task_of(se); + struct rq *rq = task_rq(p); + + return &rq->cfs; +} + +/* runqueue "owned" by this group */ +static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp) +{ + return NULL; +} + +static inline struct cfs_rq *cpu_cfs_rq(struct cfs_rq *cfs_rq, int this_cpu) +{ + return &cpu_rq(this_cpu)->cfs; +} + +#define for_each_leaf_cfs_rq(rq, cfs_rq) \ + for (cfs_rq = &rq->cfs; cfs_rq; cfs_rq = NULL) + +static inline int is_same_group(struct task_struct *curr, struct task_struct *p) +{ + return 1; +} + +#endif /* CONFIG_FAIR_GROUP_SCHED */ + +/* + * The enqueue_task method is called before nr_running is + * increased. Here we update the fair scheduling stats and + * then put the task into the rbtree: + */ +static void +enqueue_task_fair(struct rq *rq, struct task_struct *p, int wakeup, u64 now) +{ + struct cfs_rq *cfs_rq; + struct sched_entity *se = &p->se; + + for_each_sched_entity(se) { + if (se->on_rq) + break; + cfs_rq = cfs_rq_of(se); + enqueue_entity(cfs_rq, se, wakeup, now); + } +} + +/* + * The dequeue_task method is called before nr_running is + * decreased. We remove the task from the rbtree and + * update the fair scheduling stats: + */ +static void +dequeue_task_fair(struct rq *rq, struct task_struct *p, int sleep, u64 now) +{ + struct cfs_rq *cfs_rq; + struct sched_entity *se = &p->se; + + for_each_sched_entity(se) { + cfs_rq = cfs_rq_of(se); + dequeue_entity(cfs_rq, se, sleep, now); + /* Don't dequeue parent if it has other entities besides us */ + if (cfs_rq->load.weight) + break; + } +} + +/* + * sched_yield() support is very simple - we dequeue and enqueue + */ +static void yield_task_fair(struct rq *rq, struct task_struct *p) +{ + struct cfs_rq *cfs_rq = task_cfs_rq(p); + u64 now = __rq_clock(rq); + + /* + * Dequeue and enqueue the task to update its + * position within the tree: + */ + dequeue_entity(cfs_rq, &p->se, 0, now); + enqueue_entity(cfs_rq, &p->se, 0, now); +} + +/* + * Preempt the current task with a newly woken task if needed: + */ +static void check_preempt_curr_fair(struct rq *rq, struct task_struct *p) +{ + struct task_struct *curr = rq->curr; + struct cfs_rq *cfs_rq = task_cfs_rq(curr); + unsigned long gran; + + if (unlikely(rt_prio(p->prio))) { + update_curr(cfs_rq, rq_clock(rq)); + resched_task(curr); + return; + } + + gran = sysctl_sched_wakeup_granularity; + /* + * Batch tasks prefer throughput over latency: + */ + if (unlikely(p->policy == SCHED_BATCH)) + gran = sysctl_sched_batch_wakeup_granularity; + + if (is_same_group(curr, p)) + __check_preempt_curr_fair(cfs_rq, &p->se, &curr->se, gran); +} + +static struct task_struct *pick_next_task_fair(struct rq *rq, u64 now) +{ + struct cfs_rq *cfs_rq = &rq->cfs; + struct sched_entity *se; + + if (unlikely(!cfs_rq->nr_running)) + return NULL; + + do { + se = pick_next_entity(cfs_rq, now); + cfs_rq = group_cfs_rq(se); + } while (cfs_rq); + + return task_of(se); +} + +/* + * Account for a descheduled task: + */ +static void put_prev_task_fair(struct rq *rq, struct task_struct *prev, u64 now) +{ + struct sched_entity *se = &prev->se; + struct cfs_rq *cfs_rq; + + for_each_sched_entity(se) { + cfs_rq = cfs_rq_of(se); + put_prev_entity(cfs_rq, se, now); + } +} + +/************************************************** + * Fair scheduling class load-balancing methods: + */ + +/* + * Load-balancing iterator. Note: while the runqueue stays locked + * during the whole iteration, the current task might be + * dequeued so the iterator has to be dequeue-safe. Here we + * achieve that by always pre-iterating before returning + * the current task: + */ +static inline struct task_struct * +__load_balance_iterator(struct cfs_rq *cfs_rq, struct rb_node *curr) +{ + struct task_struct *p; + + if (!curr) + return NULL; + + p = rb_entry(curr, struct task_struct, se.run_node); + cfs_rq->rb_load_balance_curr = rb_next(curr); + + return p; +} + +static struct task_struct *load_balance_start_fair(void *arg) +{ + struct cfs_rq *cfs_rq = arg; + + return __load_balance_iterator(cfs_rq, first_fair(cfs_rq)); +} + +static struct task_struct *load_balance_next_fair(void *arg) +{ + struct cfs_rq *cfs_rq = arg; + + return __load_balance_iterator(cfs_rq, cfs_rq->rb_load_balance_curr); +} + +static int cfs_rq_best_prio(struct cfs_rq *cfs_rq) +{ + struct sched_entity *curr; + struct task_struct *p; + + if (!cfs_rq->nr_running) + return MAX_PRIO; + + curr = __pick_next_entity(cfs_rq); + p = task_of(curr); + + return p->prio; +} + +static int +load_balance_fair(struct rq *this_rq, int this_cpu, struct rq *busiest, + unsigned long max_nr_move, unsigned long max_load_move, + struct sched_domain *sd, enum cpu_idle_type idle, + int *all_pinned, unsigned long *total_load_moved) +{ + struct cfs_rq *busy_cfs_rq; + unsigned long load_moved, total_nr_moved = 0, nr_moved; + long rem_load_move = max_load_move; + struct rq_iterator cfs_rq_iterator; + + cfs_rq_iterator.start = load_balance_start_fair; + cfs_rq_iterator.next = load_balance_next_fair; + + for_each_leaf_cfs_rq(busiest, busy_cfs_rq) { + struct cfs_rq *this_cfs_rq; + long imbalance; + unsigned long maxload; + int this_best_prio, best_prio, best_prio_seen = 0; + + this_cfs_rq = cpu_cfs_rq(busy_cfs_rq, this_cpu); + + imbalance = busy_cfs_rq->load.weight - + this_cfs_rq->load.weight; + /* Don't pull if this_cfs_rq has more load than busy_cfs_rq */ + if (imbalance <= 0) + continue; + + /* Don't pull more than imbalance/2 */ + imbalance /= 2; + maxload = min(rem_load_move, imbalance); + + this_best_prio = cfs_rq_best_prio(this_cfs_rq); + best_prio = cfs_rq_best_prio(busy_cfs_rq); + + /* + * Enable handling of the case where there is more than one task + * with the best priority. If the current running task is one + * of those with prio==best_prio we know it won't be moved + * and therefore it's safe to override the skip (based on load) + * of any task we find with that prio. + */ + if (cfs_rq_curr(busy_cfs_rq) == &busiest->curr->se) + best_prio_seen = 1; + + /* pass busy_cfs_rq argument into + * load_balance_[start|next]_fair iterators + */ + cfs_rq_iterator.arg = busy_cfs_rq; + nr_moved = balance_tasks(this_rq, this_cpu, busiest, + max_nr_move, maxload, sd, idle, all_pinned, + &load_moved, this_best_prio, best_prio, + best_prio_seen, &cfs_rq_iterator); + + total_nr_moved += nr_moved; + max_nr_move -= nr_moved; + rem_load_move -= load_moved; + + if (max_nr_move <= 0 || rem_load_move <= 0) + break; + } + + *total_load_moved = max_load_move - rem_load_move; + + return total_nr_moved; +} + +/* + * scheduler tick hitting a task of our scheduling class: + */ +static void task_tick_fair(struct rq *rq, struct task_struct *curr) +{ + struct cfs_rq *cfs_rq; + struct sched_entity *se = &curr->se; + + for_each_sched_entity(se) { + cfs_rq = cfs_rq_of(se); + entity_tick(cfs_rq, se); + } +} + +/* + * Share the fairness runtime between parent and child, thus the + * total amount of pressure for CPU stays equal - new tasks + * get a chance to run but frequent forkers are not allowed to + * monopolize the CPU. Note: the parent runqueue is locked, + * the child is not running yet. + */ +static void task_new_fair(struct rq *rq, struct task_struct *p) +{ + struct cfs_rq *cfs_rq = task_cfs_rq(p); + struct sched_entity *se = &p->se; + u64 now = rq_clock(rq); + + sched_info_queued(p); + + update_stats_enqueue(cfs_rq, se, now); + /* + * Child runs first: we let it run before the parent + * until it reschedules once. We set up the key so that + * it will preempt the parent: + */ + p->se.fair_key = current->se.fair_key - + niced_granularity(&rq->curr->se, sysctl_sched_granularity) - 1; + /* + * The first wait is dominated by the child-runs-first logic, + * so do not credit it with that waiting time yet: + */ + if (sysctl_sched_features & SCHED_FEAT_SKIP_INITIAL) + p->se.wait_start_fair = 0; + + /* + * The statistical average of wait_runtime is about + * -granularity/2, so initialize the task with that: + */ + if (sysctl_sched_features & SCHED_FEAT_START_DEBIT) + p->se.wait_runtime = -(sysctl_sched_granularity / 2); + + __enqueue_entity(cfs_rq, se); + inc_nr_running(p, rq, now); +} + +#ifdef CONFIG_FAIR_GROUP_SCHED +/* Account for a task changing its policy or group. + * + * This routine is mostly called to set cfs_rq->curr field when a task + * migrates between groups/classes. + */ +static void set_curr_task_fair(struct rq *rq) +{ + struct task_struct *curr = rq->curr; + struct sched_entity *se = &curr->se; + u64 now = rq_clock(rq); + struct cfs_rq *cfs_rq; + + for_each_sched_entity(se) { + cfs_rq = cfs_rq_of(se); + set_next_entity(cfs_rq, se, now); + } +} +#else +static void set_curr_task_fair(struct rq *rq) +{ +} +#endif + +/* + * All the scheduling class methods: + */ +struct sched_class fair_sched_class __read_mostly = { + .enqueue_task = enqueue_task_fair, + .dequeue_task = dequeue_task_fair, + .yield_task = yield_task_fair, + + .check_preempt_curr = check_preempt_curr_fair, + + .pick_next_task = pick_next_task_fair, + .put_prev_task = put_prev_task_fair, + + .load_balance = load_balance_fair, + + .set_curr_task = set_curr_task_fair, + .task_tick = task_tick_fair, + .task_new = task_new_fair, +}; + +#ifdef CONFIG_SCHED_DEBUG +void print_cfs_stats(struct seq_file *m, int cpu, u64 now) +{ + struct rq *rq = cpu_rq(cpu); + struct cfs_rq *cfs_rq; + + for_each_leaf_cfs_rq(rq, cfs_rq) + print_cfs_rq(m, cpu, cfs_rq, now); +} +#endif -- cgit v1.2.3 From 20b8a59f2461e1be911dce2cfafefab9d22e4eee Mon Sep 17 00:00:00 2001 From: Ingo Molnar Date: Mon, 9 Jul 2007 18:51:58 +0200 Subject: sched: cfs, core data types add the CFS data types to sched.h. (the old scheduler is still fully intact.) Signed-off-by: Ingo Molnar --- include/linux/sched.h | 82 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 82 insertions(+) (limited to 'include/linux/sched.h') diff --git a/include/linux/sched.h b/include/linux/sched.h index 90420321994f..995eb407c234 100644 --- a/include/linux/sched.h +++ b/include/linux/sched.h @@ -820,6 +820,86 @@ enum sleep_type { }; struct prio_array; +struct rq; +struct sched_domain; + +struct sched_class { + struct sched_class *next; + + void (*enqueue_task) (struct rq *rq, struct task_struct *p, + int wakeup, u64 now); + void (*dequeue_task) (struct rq *rq, struct task_struct *p, + int sleep, u64 now); + void (*yield_task) (struct rq *rq, struct task_struct *p); + + void (*check_preempt_curr) (struct rq *rq, struct task_struct *p); + + struct task_struct * (*pick_next_task) (struct rq *rq, u64 now); + void (*put_prev_task) (struct rq *rq, struct task_struct *p, u64 now); + + int (*load_balance) (struct rq *this_rq, int this_cpu, + struct rq *busiest, + unsigned long max_nr_move, unsigned long max_load_move, + struct sched_domain *sd, enum cpu_idle_type idle, + int *all_pinned, unsigned long *total_load_moved); + + void (*set_curr_task) (struct rq *rq); + void (*task_tick) (struct rq *rq, struct task_struct *p); + void (*task_new) (struct rq *rq, struct task_struct *p); +}; + +struct load_weight { + unsigned long weight, inv_weight; +}; + +/* + * CFS stats for a schedulable entity (task, task-group etc) + * + * Current field usage histogram: + * + * 4 se->block_start + * 4 se->run_node + * 4 se->sleep_start + * 4 se->sleep_start_fair + * 6 se->load.weight + * 7 se->delta_fair + * 15 se->wait_runtime + */ +struct sched_entity { + long wait_runtime; + unsigned long delta_fair_run; + unsigned long delta_fair_sleep; + unsigned long delta_exec; + s64 fair_key; + struct load_weight load; /* for load-balancing */ + struct rb_node run_node; + unsigned int on_rq; + + u64 wait_start_fair; + u64 wait_start; + u64 exec_start; + u64 sleep_start; + u64 sleep_start_fair; + u64 block_start; + u64 sleep_max; + u64 block_max; + u64 exec_max; + u64 wait_max; + u64 last_ran; + + u64 sum_exec_runtime; + s64 sum_wait_runtime; + s64 sum_sleep_runtime; + unsigned long wait_runtime_overruns; + unsigned long wait_runtime_underruns; +#ifdef CONFIG_FAIR_GROUP_SCHED + struct sched_entity *parent; + /* rq on which this entity is (to be) queued: */ + struct cfs_rq *cfs_rq; + /* rq "owned" by this entity/group: */ + struct cfs_rq *my_q; +#endif +}; struct task_struct { volatile long state; /* -1 unrunnable, 0 runnable, >0 stopped */ @@ -839,6 +919,8 @@ struct task_struct { int prio, static_prio, normal_prio; struct list_head run_list; struct prio_array *array; + struct sched_class *sched_class; + struct sched_entity se; unsigned short ioprio; #ifdef CONFIG_BLK_DEV_IO_TRACE -- cgit v1.2.3 From 41b86e9c510ae66639bf29d3201e1d2384a7fde6 Mon Sep 17 00:00:00 2001 From: Ingo Molnar Date: Mon, 9 Jul 2007 18:51:58 +0200 Subject: sched: make posix-cpu-timers use CFS's accounting information update the posix-cpu-timers code to use CFS's CPU accounting information. Signed-off-by: Ingo Molnar --- include/linux/sched.h | 5 +++-- kernel/posix-cpu-timers.c | 34 +++++++++++++++++----------------- kernel/sched.c | 36 +++++++++++++----------------------- 3 files changed, 33 insertions(+), 42 deletions(-) (limited to 'include/linux/sched.h') diff --git a/include/linux/sched.h b/include/linux/sched.h index 995eb407c234..3e7f1890e55d 100644 --- a/include/linux/sched.h +++ b/include/linux/sched.h @@ -482,7 +482,8 @@ struct signal_struct { * from jiffies_to_ns(utime + stime) if sched_clock uses something * other than jiffies.) */ - unsigned long long sched_time; + unsigned long sched_time; + unsigned long long sum_sched_runtime; /* * We don't bother to synchronize most readers of this at all, @@ -1308,7 +1309,7 @@ static inline int set_cpus_allowed(struct task_struct *p, cpumask_t new_mask) extern unsigned long long sched_clock(void); extern unsigned long long -current_sched_time(const struct task_struct *current_task); +task_sched_runtime(struct task_struct *task); /* sched_exec is called by processes performing an exec */ #ifdef CONFIG_SMP diff --git a/kernel/posix-cpu-timers.c b/kernel/posix-cpu-timers.c index 1de710e18373..b53c8fcd9d82 100644 --- a/kernel/posix-cpu-timers.c +++ b/kernel/posix-cpu-timers.c @@ -161,7 +161,7 @@ static inline cputime_t virt_ticks(struct task_struct *p) } static inline unsigned long long sched_ns(struct task_struct *p) { - return (p == current) ? current_sched_time(p) : p->sched_time; + return task_sched_runtime(p); } int posix_cpu_clock_getres(const clockid_t which_clock, struct timespec *tp) @@ -246,10 +246,10 @@ static int cpu_clock_sample_group_locked(unsigned int clock_idx, } while (t != p); break; case CPUCLOCK_SCHED: - cpu->sched = p->signal->sched_time; + cpu->sched = p->signal->sum_sched_runtime; /* Add in each other live thread. */ while ((t = next_thread(t)) != p) { - cpu->sched += t->sched_time; + cpu->sched += t->se.sum_exec_runtime; } cpu->sched += sched_ns(p); break; @@ -422,7 +422,7 @@ int posix_cpu_timer_del(struct k_itimer *timer) */ static void cleanup_timers(struct list_head *head, cputime_t utime, cputime_t stime, - unsigned long long sched_time) + unsigned long long sum_exec_runtime) { struct cpu_timer_list *timer, *next; cputime_t ptime = cputime_add(utime, stime); @@ -451,10 +451,10 @@ static void cleanup_timers(struct list_head *head, ++head; list_for_each_entry_safe(timer, next, head, entry) { list_del_init(&timer->entry); - if (timer->expires.sched < sched_time) { + if (timer->expires.sched < sum_exec_runtime) { timer->expires.sched = 0; } else { - timer->expires.sched -= sched_time; + timer->expires.sched -= sum_exec_runtime; } } } @@ -467,7 +467,7 @@ static void cleanup_timers(struct list_head *head, void posix_cpu_timers_exit(struct task_struct *tsk) { cleanup_timers(tsk->cpu_timers, - tsk->utime, tsk->stime, tsk->sched_time); + tsk->utime, tsk->stime, tsk->se.sum_exec_runtime); } void posix_cpu_timers_exit_group(struct task_struct *tsk) @@ -475,7 +475,7 @@ void posix_cpu_timers_exit_group(struct task_struct *tsk) cleanup_timers(tsk->signal->cpu_timers, cputime_add(tsk->utime, tsk->signal->utime), cputime_add(tsk->stime, tsk->signal->stime), - tsk->sched_time + tsk->signal->sched_time); + tsk->se.sum_exec_runtime + tsk->signal->sum_sched_runtime); } @@ -536,7 +536,7 @@ static void process_timer_rebalance(struct task_struct *p, nsleft = max_t(unsigned long long, nsleft, 1); do { if (likely(!(t->flags & PF_EXITING))) { - ns = t->sched_time + nsleft; + ns = t->se.sum_exec_runtime + nsleft; if (t->it_sched_expires == 0 || t->it_sched_expires > ns) { t->it_sched_expires = ns; @@ -1004,7 +1004,7 @@ static void check_thread_timers(struct task_struct *tsk, struct cpu_timer_list *t = list_first_entry(timers, struct cpu_timer_list, entry); - if (!--maxfire || tsk->sched_time < t->expires.sched) { + if (!--maxfire || tsk->se.sum_exec_runtime < t->expires.sched) { tsk->it_sched_expires = t->expires.sched; break; } @@ -1024,7 +1024,7 @@ static void check_process_timers(struct task_struct *tsk, int maxfire; struct signal_struct *const sig = tsk->signal; cputime_t utime, stime, ptime, virt_expires, prof_expires; - unsigned long long sched_time, sched_expires; + unsigned long long sum_sched_runtime, sched_expires; struct task_struct *t; struct list_head *timers = sig->cpu_timers; @@ -1044,12 +1044,12 @@ static void check_process_timers(struct task_struct *tsk, */ utime = sig->utime; stime = sig->stime; - sched_time = sig->sched_time; + sum_sched_runtime = sig->sum_sched_runtime; t = tsk; do { utime = cputime_add(utime, t->utime); stime = cputime_add(stime, t->stime); - sched_time += t->sched_time; + sum_sched_runtime += t->se.sum_exec_runtime; t = next_thread(t); } while (t != tsk); ptime = cputime_add(utime, stime); @@ -1090,7 +1090,7 @@ static void check_process_timers(struct task_struct *tsk, struct cpu_timer_list *t = list_first_entry(timers, struct cpu_timer_list, entry); - if (!--maxfire || sched_time < t->expires.sched) { + if (!--maxfire || sum_sched_runtime < t->expires.sched) { sched_expires = t->expires.sched; break; } @@ -1182,7 +1182,7 @@ static void check_process_timers(struct task_struct *tsk, virt_left = cputime_sub(virt_expires, utime); virt_left = cputime_div_non_zero(virt_left, nthreads); if (sched_expires) { - sched_left = sched_expires - sched_time; + sched_left = sched_expires - sum_sched_runtime; do_div(sched_left, nthreads); sched_left = max_t(unsigned long long, sched_left, 1); } else { @@ -1208,7 +1208,7 @@ static void check_process_timers(struct task_struct *tsk, t->it_virt_expires = ticks; } - sched = t->sched_time + sched_left; + sched = t->se.sum_exec_runtime + sched_left; if (sched_expires && (t->it_sched_expires == 0 || t->it_sched_expires > sched)) { t->it_sched_expires = sched; @@ -1300,7 +1300,7 @@ void run_posix_cpu_timers(struct task_struct *tsk) if (UNEXPIRED(prof) && UNEXPIRED(virt) && (tsk->it_sched_expires == 0 || - tsk->sched_time < tsk->it_sched_expires)) + tsk->se.sum_exec_runtime < tsk->it_sched_expires)) return; #undef UNEXPIRED diff --git a/kernel/sched.c b/kernel/sched.c index 29eb227e33f7..0333abdda85e 100644 --- a/kernel/sched.c +++ b/kernel/sched.c @@ -3156,28 +3156,23 @@ DEFINE_PER_CPU(struct kernel_stat, kstat); EXPORT_PER_CPU_SYMBOL(kstat); /* - * This is called on clock ticks and on context switches. - * Bank in p->sched_time the ns elapsed since the last tick or switch. + * Return p->sum_exec_runtime plus any more ns on the sched_clock + * that have not yet been banked in case the task is currently running. */ -static inline void -update_cpu_clock(struct task_struct *p, struct rq *rq, unsigned long long now) +unsigned long long task_sched_runtime(struct task_struct *p) { - p->sched_time += now - p->last_ran; - p->last_ran = rq->most_recent_timestamp = now; -} - -/* - * Return current->sched_time plus any more ns on the sched_clock - * that have not yet been banked. - */ -unsigned long long current_sched_time(const struct task_struct *p) -{ - unsigned long long ns; unsigned long flags; + u64 ns, delta_exec; + struct rq *rq; - local_irq_save(flags); - ns = p->sched_time + sched_clock() - p->last_ran; - local_irq_restore(flags); + rq = task_rq_lock(p, &flags); + ns = p->se.sum_exec_runtime; + if (rq->curr == p) { + delta_exec = rq_clock(rq) - p->se.exec_start; + if ((s64)delta_exec > 0) + ns += delta_exec; + } + task_rq_unlock(rq, &flags); return ns; } @@ -3360,14 +3355,11 @@ out_unlock: */ void scheduler_tick(void) { - unsigned long long now = sched_clock(); struct task_struct *p = current; int cpu = smp_processor_id(); int idle_at_tick = idle_cpu(cpu); struct rq *rq = cpu_rq(cpu); - update_cpu_clock(p, rq, now); - if (!idle_at_tick) task_running_tick(rq, p); #ifdef CONFIG_SMP @@ -3550,8 +3542,6 @@ switch_tasks: clear_tsk_need_resched(prev); rcu_qsctr_inc(task_cpu(prev)); - update_cpu_clock(prev, rq, now); - prev->sleep_avg -= run_time; if ((long)prev->sleep_avg <= 0) prev->sleep_avg = 0; -- cgit v1.2.3 From e05606d3301525aa67b081ad9fccade2b31ab35a Mon Sep 17 00:00:00 2001 From: Ingo Molnar Date: Mon, 9 Jul 2007 18:51:59 +0200 Subject: sched: clean up the rt priority macros clean up the rt priority macros, pointed out by Andrew Morton. Signed-off-by: Ingo Molnar --- include/linux/sched.h | 61 ++++++++++++++++++++++++++++++--------------------- kernel/exit.c | 2 +- kernel/sched.c | 22 ++++++++++++++----- 3 files changed, 54 insertions(+), 31 deletions(-) (limited to 'include/linux/sched.h') diff --git a/include/linux/sched.h b/include/linux/sched.h index 3e7f1890e55d..4dcc61cca00a 100644 --- a/include/linux/sched.h +++ b/include/linux/sched.h @@ -525,31 +525,6 @@ struct signal_struct { #define SIGNAL_STOP_CONTINUED 0x00000004 /* SIGCONT since WCONTINUED reap */ #define SIGNAL_GROUP_EXIT 0x00000008 /* group exit in progress */ - -/* - * Priority of a process goes from 0..MAX_PRIO-1, valid RT - * priority is 0..MAX_RT_PRIO-1, and SCHED_NORMAL/SCHED_BATCH - * tasks are in the range MAX_RT_PRIO..MAX_PRIO-1. Priority - * values are inverted: lower p->prio value means higher priority. - * - * The MAX_USER_RT_PRIO value allows the actual maximum - * RT priority to be separate from the value exported to - * user-space. This allows kernel threads to set their - * priority to a value higher than any user task. Note: - * MAX_RT_PRIO must not be smaller than MAX_USER_RT_PRIO. - */ - -#define MAX_USER_RT_PRIO 100 -#define MAX_RT_PRIO MAX_USER_RT_PRIO - -#define MAX_PRIO (MAX_RT_PRIO + 40) - -#define rt_prio(prio) unlikely((prio) < MAX_RT_PRIO) -#define rt_task(p) rt_prio((p)->prio) -#define batch_task(p) (unlikely((p)->policy == SCHED_BATCH)) -#define is_rt_policy(p) ((p) != SCHED_NORMAL && (p) != SCHED_BATCH) -#define has_rt_policy(p) unlikely(is_rt_policy((p)->policy)) - /* * Some day this will be a full-fledged user tracking system.. */ @@ -1164,6 +1139,42 @@ struct task_struct { #endif }; +/* + * Priority of a process goes from 0..MAX_PRIO-1, valid RT + * priority is 0..MAX_RT_PRIO-1, and SCHED_NORMAL/SCHED_BATCH + * tasks are in the range MAX_RT_PRIO..MAX_PRIO-1. Priority + * values are inverted: lower p->prio value means higher priority. + * + * The MAX_USER_RT_PRIO value allows the actual maximum + * RT priority to be separate from the value exported to + * user-space. This allows kernel threads to set their + * priority to a value higher than any user task. Note: + * MAX_RT_PRIO must not be smaller than MAX_USER_RT_PRIO. + */ + +#define MAX_USER_RT_PRIO 100 +#define MAX_RT_PRIO MAX_USER_RT_PRIO + +#define MAX_PRIO (MAX_RT_PRIO + 40) +#define DEFAULT_PRIO (MAX_RT_PRIO + 20) + +static inline int rt_prio(int prio) +{ + if (unlikely(prio < MAX_RT_PRIO)) + return 1; + return 0; +} + +static inline int rt_task(struct task_struct *p) +{ + return rt_prio(p->prio); +} + +static inline int batch_task(struct task_struct *p) +{ + return p->policy == SCHED_BATCH; +} + static inline pid_t process_group(struct task_struct *tsk) { return tsk->signal->pgrp; diff --git a/kernel/exit.c b/kernel/exit.c index 6c7699240327..8fd7acd7bbd0 100644 --- a/kernel/exit.c +++ b/kernel/exit.c @@ -290,7 +290,7 @@ static void reparent_to_kthreadd(void) /* Set the exit signal to SIGCHLD so we signal init on exit */ current->exit_signal = SIGCHLD; - if (!has_rt_policy(current) && (task_nice(current) < 0)) + if (task_nice(current) < 0) set_user_nice(current, 0); /* cpus_allowed? */ /* rt_priority? */ diff --git a/kernel/sched.c b/kernel/sched.c index d9ed9274bf0a..53c0ee742f69 100644 --- a/kernel/sched.c +++ b/kernel/sched.c @@ -220,6 +220,18 @@ static inline unsigned int task_timeslice(struct task_struct *p) return static_prio_timeslice(p->static_prio); } +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: */ @@ -698,7 +710,7 @@ static inline int __normal_prio(struct task_struct *p) static void set_load_weight(struct task_struct *p) { - if (has_rt_policy(p)) { + if (task_has_rt_policy(p)) { #ifdef CONFIG_SMP if (p == task_rq(p)->migration_thread) /* @@ -749,7 +761,7 @@ static inline int normal_prio(struct task_struct *p) { int prio; - if (has_rt_policy(p)) + if (task_has_rt_policy(p)) prio = MAX_RT_PRIO-1 - p->rt_priority; else prio = __normal_prio(p); @@ -4051,7 +4063,7 @@ void set_user_nice(struct task_struct *p, long nice) * it wont have any effect on scheduling until the task is * not SCHED_NORMAL/SCHED_BATCH: */ - if (has_rt_policy(p)) { + if (task_has_rt_policy(p)) { p->static_prio = NICE_TO_PRIO(nice); goto out_unlock; } @@ -4240,14 +4252,14 @@ recheck: (p->mm && param->sched_priority > MAX_USER_RT_PRIO-1) || (!p->mm && param->sched_priority > MAX_RT_PRIO-1)) return -EINVAL; - if (is_rt_policy(policy) != (param->sched_priority != 0)) + if (rt_policy(policy) != (param->sched_priority != 0)) return -EINVAL; /* * Allow unprivileged RT tasks to decrease priority: */ if (!capable(CAP_SYS_NICE)) { - if (is_rt_policy(policy)) { + if (rt_policy(policy)) { unsigned long rlim_rtprio; unsigned long flags; -- cgit v1.2.3 From f2ac58ee617fd9f6cd9922fbcd291b661d7c9954 Mon Sep 17 00:00:00 2001 From: Ingo Molnar Date: Mon, 9 Jul 2007 18:51:59 +0200 Subject: sched: remove sleep_type remove the sleep_type heuristics from the core scheduler - scheduling policy is implemented in the scheduling-policy modules. (and CFS does not use this type of sleep-type heuristics) Signed-off-by: Ingo Molnar --- include/linux/sched.h | 8 ----- kernel/sched.c | 91 ++------------------------------------------------- 2 files changed, 2 insertions(+), 97 deletions(-) (limited to 'include/linux/sched.h') diff --git a/include/linux/sched.h b/include/linux/sched.h index 4dcc61cca00a..be2460e6f55b 100644 --- a/include/linux/sched.h +++ b/include/linux/sched.h @@ -788,13 +788,6 @@ struct mempolicy; struct pipe_inode_info; struct uts_namespace; -enum sleep_type { - SLEEP_NORMAL, - SLEEP_NONINTERACTIVE, - SLEEP_INTERACTIVE, - SLEEP_INTERRUPTED, -}; - struct prio_array; struct rq; struct sched_domain; @@ -905,7 +898,6 @@ struct task_struct { unsigned long sleep_avg; unsigned long long timestamp, last_ran; unsigned long long sched_time; /* sched_clock time spent running */ - enum sleep_type sleep_type; unsigned int policy; cpumask_t cpus_allowed; diff --git a/kernel/sched.c b/kernel/sched.c index 6e5a89ba4f76..26795adab3ad 100644 --- a/kernel/sched.c +++ b/kernel/sched.c @@ -990,32 +990,7 @@ static int recalc_task_prio(struct task_struct *p, unsigned long long now) * with one single large enough sleep. */ p->sleep_avg = ceiling; - /* - * Using INTERACTIVE_SLEEP() as a ceiling places a - * nice(0) task 1ms sleep away from promotion, and - * gives it 700ms to round-robin with no chance of - * being demoted. This is more than generous, so - * mark this sleep as non-interactive to prevent the - * on-runqueue bonus logic from intervening should - * this task not receive cpu immediately. - */ - p->sleep_type = SLEEP_NONINTERACTIVE; } else { - /* - * Tasks waking from uninterruptible sleep are - * limited in their sleep_avg rise as they - * are likely to be waiting on I/O - */ - if (p->sleep_type == SLEEP_NONINTERACTIVE && p->mm) { - if (p->sleep_avg >= ceiling) - sleep_time = 0; - else if (p->sleep_avg + sleep_time >= - ceiling) { - p->sleep_avg = ceiling; - sleep_time = 0; - } - } - /* * This code gives a bonus to interactive tasks. * @@ -1069,29 +1044,6 @@ static void activate_task(struct task_struct *p, struct rq *rq, int local) } p->prio = recalc_task_prio(p, now); - - /* - * This checks to make sure it's not an uninterruptible task - * that is now waking up. - */ - if (p->sleep_type == SLEEP_NORMAL) { - /* - * Tasks which were woken up by interrupts (ie. hw events) - * are most likely of interactive nature. So we give them - * the credit of extending their sleep time to the period - * of time they spend on the runqueue, waiting for execution - * on a CPU, first time around: - */ - if (in_interrupt()) - p->sleep_type = SLEEP_INTERRUPTED; - else { - /* - * Normal first-time wakeups get a credit too for - * on-runqueue time, but it will be weighted down: - */ - p->sleep_type = SLEEP_INTERACTIVE; - } - } p->timestamp = now; out: __activate_task(p, rq); @@ -1641,23 +1593,8 @@ out_set_cpu: out_activate: #endif /* CONFIG_SMP */ - if (old_state == TASK_UNINTERRUPTIBLE) { + if (old_state == TASK_UNINTERRUPTIBLE) rq->nr_uninterruptible--; - /* - * Tasks on involuntary sleep don't earn - * sleep_avg beyond just interactive state. - */ - p->sleep_type = SLEEP_NONINTERACTIVE; - } else - - /* - * Tasks that have marked their sleep as noninteractive get - * woken up with their sleep average not weighted in an - * interactive way. - */ - if (old_state & TASK_NONINTERACTIVE) - p->sleep_type = SLEEP_NONINTERACTIVE; - activate_task(p, rq, cpu == this_cpu); /* @@ -3533,12 +3470,6 @@ EXPORT_SYMBOL(sub_preempt_count); #endif -static inline int interactive_sleep(enum sleep_type sleep_type) -{ - return (sleep_type == SLEEP_INTERACTIVE || - sleep_type == SLEEP_INTERRUPTED); -} - /* * schedule() is the main scheduler function. */ @@ -3549,7 +3480,7 @@ asmlinkage void __sched schedule(void) struct list_head *queue; unsigned long long now; unsigned long run_time; - int cpu, idx, new_prio; + int cpu, idx; long *switch_count; struct rq *rq; @@ -3642,24 +3573,6 @@ need_resched_nonpreemptible: queue = array->queue + idx; next = list_entry(queue->next, struct task_struct, run_list); - if (!rt_task(next) && interactive_sleep(next->sleep_type)) { - unsigned long long delta = now - next->timestamp; - if (unlikely((long long)(now - next->timestamp) < 0)) - delta = 0; - - if (next->sleep_type == SLEEP_INTERACTIVE) - delta = delta * (ON_RUNQUEUE_WEIGHT * 128 / 100) / 128; - - array = next->array; - new_prio = recalc_task_prio(next, next->timestamp + delta); - - if (unlikely(next->prio != new_prio)) { - dequeue_task(next, array); - next->prio = new_prio; - enqueue_task(next, array); - } - } - next->sleep_type = SLEEP_NORMAL; switch_tasks: if (next == rq->idle) schedstat_inc(rq, sched_goidle); -- cgit v1.2.3 From bb29ab26863c022743143f27956cc0ca362f258c Mon Sep 17 00:00:00 2001 From: Ingo Molnar Date: Mon, 9 Jul 2007 18:51:59 +0200 Subject: sched: x86, track TSC-unstable events track TSC-unstable events and propagate it to the scheduler code. Also allow sched_clock() to be used when the TSC is unstable, the rq_clock() wrapper creates a reliable clock out of it. Signed-off-by: Ingo Molnar --- arch/i386/kernel/tsc.c | 9 ++++++++- include/linux/sched.h | 2 ++ kernel/sched.c | 7 +++++++ 3 files changed, 17 insertions(+), 1 deletion(-) (limited to 'include/linux/sched.h') diff --git a/arch/i386/kernel/tsc.c b/arch/i386/kernel/tsc.c index f64b81f3033b..ea63a30ca3e8 100644 --- a/arch/i386/kernel/tsc.c +++ b/arch/i386/kernel/tsc.c @@ -4,6 +4,7 @@ * See comments there for proper credits. */ +#include #include #include #include @@ -106,8 +107,13 @@ unsigned long long sched_clock(void) /* * Fall back to jiffies if there's no TSC available: + * ( But note that we still use it if the TSC is marked + * unstable. We do this because unlike Time Of Day, + * the scheduler clock tolerates small errors and it's + * very important for it to be as fast as the platform + * can achive it. ) */ - if (unlikely(!tsc_enabled)) + if (unlikely(!tsc_enabled && !tsc_unstable)) /* No locking but a rare wrong value is not a big deal: */ return (jiffies_64 - INITIAL_JIFFIES) * (1000000000 / HZ); @@ -277,6 +283,7 @@ static struct clocksource clocksource_tsc = { void mark_tsc_unstable(char *reason) { + sched_clock_unstable_event(); if (!tsc_unstable) { tsc_unstable = 1; tsc_enabled = 0; diff --git a/include/linux/sched.h b/include/linux/sched.h index be2460e6f55b..fa895b309da0 100644 --- a/include/linux/sched.h +++ b/include/linux/sched.h @@ -1321,6 +1321,8 @@ extern void sched_exec(void); #define sched_exec() {} #endif +extern void sched_clock_unstable_event(void); + #ifdef CONFIG_HOTPLUG_CPU extern void idle_task_exit(void); #else diff --git a/kernel/sched.c b/kernel/sched.c index 01ba4b1848a0..6150cd70f448 100644 --- a/kernel/sched.c +++ b/kernel/sched.c @@ -67,6 +67,13 @@ unsigned long long __attribute__((weak)) sched_clock(void) return (unsigned long long)jiffies * (1000000000 / HZ); } +/* + * CPU frequency is/was unstable - start new by setting prev_clock_raw: + */ +void sched_clock_unstable_event(void) +{ +} + /* * Convert user-nice values [ -20 ... 0 ... 19 ] * to static priority [ MAX_RT_PRIO..MAX_PRIO-1 ], -- cgit v1.2.3 From 172ba844a8851c3edd13c0a979cdf46bd5e3cc1a Mon Sep 17 00:00:00 2001 From: Balbir Singh Date: Mon, 9 Jul 2007 18:52:00 +0200 Subject: sched: update delay-accounting to use CFS's precise stats update delay-accounting to use CFS's precise stats. Signed-off-by: Ingo Molnar --- fs/proc/base.c | 2 +- include/linux/sched.h | 10 +++++----- kernel/delayacct.c | 10 +++++----- kernel/exit.c | 2 +- kernel/fork.c | 4 ++-- kernel/sched_stats.h | 2 +- 6 files changed, 15 insertions(+), 15 deletions(-) (limited to 'include/linux/sched.h') diff --git a/fs/proc/base.c b/fs/proc/base.c index a5fa1fdafc4e..0f40e820c7fd 100644 --- a/fs/proc/base.c +++ b/fs/proc/base.c @@ -296,7 +296,7 @@ static int proc_pid_wchan(struct task_struct *task, char *buffer) */ static int proc_pid_schedstat(struct task_struct *task, char *buffer) { - return sprintf(buffer, "%lu %lu %lu\n", + return sprintf(buffer, "%llu %llu %lu\n", task->sched_info.cpu_time, task->sched_info.run_delay, task->sched_info.pcnt); diff --git a/include/linux/sched.h b/include/linux/sched.h index fa895b309da0..e64dbd4cd829 100644 --- a/include/linux/sched.h +++ b/include/linux/sched.h @@ -562,13 +562,13 @@ struct reclaim_state; #if defined(CONFIG_SCHEDSTATS) || defined(CONFIG_TASK_DELAY_ACCT) struct sched_info { /* cumulative counters */ - unsigned long cpu_time, /* time spent on the cpu */ - run_delay, /* time spent waiting on a runqueue */ - pcnt; /* # of timeslices run on this cpu */ + unsigned long pcnt; /* # of times run on this cpu */ + unsigned long long cpu_time, /* time spent on the cpu */ + run_delay; /* time spent waiting on a runqueue */ /* timestamps */ - unsigned long last_arrival, /* when we last ran on a cpu */ - last_queued; /* when we were last queued to run */ + unsigned long long last_arrival,/* when we last ran on a cpu */ + last_queued; /* when we were last queued to run */ }; #endif /* defined(CONFIG_SCHEDSTATS) || defined(CONFIG_TASK_DELAY_ACCT) */ diff --git a/kernel/delayacct.c b/kernel/delayacct.c index c0148ae992c4..81e697829633 100644 --- a/kernel/delayacct.c +++ b/kernel/delayacct.c @@ -99,9 +99,10 @@ void __delayacct_blkio_end(void) int __delayacct_add_tsk(struct taskstats *d, struct task_struct *tsk) { s64 tmp; - struct timespec ts; - unsigned long t1,t2,t3; + unsigned long t1; + unsigned long long t2, t3; unsigned long flags; + struct timespec ts; /* Though tsk->delays accessed later, early exit avoids * unnecessary returning of other data @@ -124,11 +125,10 @@ int __delayacct_add_tsk(struct taskstats *d, struct task_struct *tsk) d->cpu_count += t1; - jiffies_to_timespec(t2, &ts); - tmp = (s64)d->cpu_delay_total + timespec_to_ns(&ts); + tmp = (s64)d->cpu_delay_total + t2; d->cpu_delay_total = (tmp < (s64)d->cpu_delay_total) ? 0 : tmp; - tmp = (s64)d->cpu_run_virtual_total + (s64)jiffies_to_usecs(t3) * 1000; + tmp = (s64)d->cpu_run_virtual_total + t3; d->cpu_run_virtual_total = (tmp < (s64)d->cpu_run_virtual_total) ? 0 : tmp; diff --git a/kernel/exit.c b/kernel/exit.c index 8fd7acd7bbd0..ca6a11b73023 100644 --- a/kernel/exit.c +++ b/kernel/exit.c @@ -122,9 +122,9 @@ static void __exit_signal(struct task_struct *tsk) sig->maj_flt += tsk->maj_flt; sig->nvcsw += tsk->nvcsw; sig->nivcsw += tsk->nivcsw; - sig->sched_time += tsk->sched_time; sig->inblock += task_io_get_inblock(tsk); sig->oublock += task_io_get_oublock(tsk); + sig->sum_sched_runtime += tsk->se.sum_exec_runtime; sig = NULL; /* Marker for below. */ } diff --git a/kernel/fork.c b/kernel/fork.c index 73ad5cda1bcd..da3a155bba0d 100644 --- a/kernel/fork.c +++ b/kernel/fork.c @@ -877,7 +877,7 @@ static inline int copy_signal(unsigned long clone_flags, struct task_struct * ts sig->nvcsw = sig->nivcsw = sig->cnvcsw = sig->cnivcsw = 0; sig->min_flt = sig->maj_flt = sig->cmin_flt = sig->cmaj_flt = 0; sig->inblock = sig->oublock = sig->cinblock = sig->coublock = 0; - sig->sched_time = 0; + sig->sum_sched_runtime = 0; INIT_LIST_HEAD(&sig->cpu_timers[0]); INIT_LIST_HEAD(&sig->cpu_timers[1]); INIT_LIST_HEAD(&sig->cpu_timers[2]); @@ -1040,7 +1040,7 @@ static struct task_struct *copy_process(unsigned long clone_flags, p->utime = cputime_zero; p->stime = cputime_zero; - p->sched_time = 0; + #ifdef CONFIG_TASK_XACCT p->rchar = 0; /* I/O counter: bytes read */ p->wchar = 0; /* I/O counter: bytes written */ diff --git a/kernel/sched_stats.h b/kernel/sched_stats.h index cd82c6078904..c63c38f6fa6e 100644 --- a/kernel/sched_stats.h +++ b/kernel/sched_stats.h @@ -21,7 +21,7 @@ static int show_schedstat(struct seq_file *seq, void *v) /* runqueue-specific stats */ seq_printf(seq, - "cpu%d %lu %lu %lu %lu %lu %lu %lu %lu %lu %lu %lu %lu", + "cpu%d %lu %lu %lu %lu %lu %lu %lu %lu %lu %llu %llu %lu", cpu, rq->yld_both_empty, rq->yld_act_empty, rq->yld_exp_empty, rq->yld_cnt, rq->sched_switch, rq->sched_cnt, rq->sched_goidle, -- cgit v1.2.3 From ad46c2c4ebcead75cd364a79b63b134393094fb9 Mon Sep 17 00:00:00 2001 From: Ingo Molnar Date: Mon, 9 Jul 2007 18:52:00 +0200 Subject: sched: clean up fastcall uses of sched_fork()/sched_exit() sched_fork()/sched_exit() does not need to specify fastcall anymore, as the x86 kernel defaults to regparm3, and no assembly code calls these functions. Signed-off-by: Ingo Molnar --- include/linux/sched.h | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'include/linux/sched.h') diff --git a/include/linux/sched.h b/include/linux/sched.h index e64dbd4cd829..ce0c5adc9eb0 100644 --- a/include/linux/sched.h +++ b/include/linux/sched.h @@ -1416,8 +1416,8 @@ extern void FASTCALL(wake_up_new_task(struct task_struct * tsk, #else static inline void kick_process(struct task_struct *tsk) { } #endif -extern void FASTCALL(sched_fork(struct task_struct * p, int clone_flags)); -extern void FASTCALL(sched_exit(struct task_struct * p)); +extern void sched_fork(struct task_struct *p, int clone_flags); +extern void sched_dead(struct task_struct *p); extern int in_group_p(gid_t); extern int in_egroup_p(gid_t); -- cgit v1.2.3 From 50e645a8a1a91f57dd5d8454620be5f1cb0fc089 Mon Sep 17 00:00:00 2001 From: Ingo Molnar Date: Mon, 9 Jul 2007 18:52:00 +0200 Subject: sched: remove interactivity types from sched.h remove now-unused types/fields used by the old scheduler. Signed-off-by: Ingo Molnar --- include/linux/sched.h | 9 ++------- 1 file changed, 2 insertions(+), 7 deletions(-) (limited to 'include/linux/sched.h') diff --git a/include/linux/sched.h b/include/linux/sched.h index ce0c5adc9eb0..efa3beb007ff 100644 --- a/include/linux/sched.h +++ b/include/linux/sched.h @@ -788,7 +788,6 @@ struct mempolicy; struct pipe_inode_info; struct uts_namespace; -struct prio_array; struct rq; struct sched_domain; @@ -884,10 +883,9 @@ struct task_struct { int oncpu; #endif #endif - int load_weight; /* for niceness load balancing purposes */ + int prio, static_prio, normal_prio; struct list_head run_list; - struct prio_array *array; struct sched_class *sched_class; struct sched_entity se; @@ -895,13 +893,10 @@ struct task_struct { #ifdef CONFIG_BLK_DEV_IO_TRACE unsigned int btrace_seq; #endif - unsigned long sleep_avg; - unsigned long long timestamp, last_ran; - unsigned long long sched_time; /* sched_clock time spent running */ unsigned int policy; cpumask_t cpus_allowed; - unsigned int time_slice, first_time_slice; + unsigned int time_slice; #if defined(CONFIG_SCHEDSTATS) || defined(CONFIG_TASK_DELAY_ACCT) struct sched_info sched_info; -- cgit v1.2.3 From 0c57d5893e4a9857ff22ec9e379f6bdbdad50850 Mon Sep 17 00:00:00 2001 From: Ingo Molnar Date: Mon, 9 Jul 2007 18:52:00 +0200 Subject: sched: remove batch_task() batch_task() in sched.h is now unused - remove it. Signed-off-by: Ingo Molnar --- include/linux/sched.h | 5 ----- 1 file changed, 5 deletions(-) (limited to 'include/linux/sched.h') diff --git a/include/linux/sched.h b/include/linux/sched.h index efa3beb007ff..aa582be8cafa 100644 --- a/include/linux/sched.h +++ b/include/linux/sched.h @@ -1157,11 +1157,6 @@ static inline int rt_task(struct task_struct *p) return rt_prio(p->prio); } -static inline int batch_task(struct task_struct *p) -{ - return p->policy == SCHED_BATCH; -} - static inline pid_t process_group(struct task_struct *tsk) { return tsk->signal->pgrp; -- cgit v1.2.3 From 7dd593608df3f9d4e4531cfe29f28c3a3766a0ee Mon Sep 17 00:00:00 2001 From: Ingo Molnar Date: Mon, 9 Jul 2007 18:52:00 +0200 Subject: sched: remove old cpu accounting field remove the old cpu-accounting field from signal_struct, now that the code is using CFS's stats. Signed-off-by: Ingo Molnar --- include/linux/sched.h | 1 - 1 file changed, 1 deletion(-) (limited to 'include/linux/sched.h') diff --git a/include/linux/sched.h b/include/linux/sched.h index aa582be8cafa..c9d65738bb7a 100644 --- a/include/linux/sched.h +++ b/include/linux/sched.h @@ -482,7 +482,6 @@ struct signal_struct { * from jiffies_to_ns(utime + stime) if sched_clock uses something * other than jiffies.) */ - unsigned long sched_time; unsigned long long sum_sched_runtime; /* -- cgit v1.2.3 From 43ae34cb4cd650d1eb4460a8253a8e747ba052ac Mon Sep 17 00:00:00 2001 From: Ingo Molnar Date: Mon, 9 Jul 2007 18:52:00 +0200 Subject: sched: scheduler debugging, core scheduler debugging core: implement /proc/sched_debug and /proc//sched files for scheduler debugging. Signed-off-by: Ingo Molnar --- fs/proc/base.c | 69 +++++++++++++ include/linux/sched.h | 20 ++++ kernel/sched_debug.c | 275 ++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 364 insertions(+) create mode 100644 kernel/sched_debug.c (limited to 'include/linux/sched.h') diff --git a/fs/proc/base.c b/fs/proc/base.c index 0f40e820c7fd..46ea5d56e1bb 100644 --- a/fs/proc/base.c +++ b/fs/proc/base.c @@ -929,6 +929,69 @@ static const struct file_operations proc_fault_inject_operations = { }; #endif +#ifdef CONFIG_SCHED_DEBUG +/* + * Print out various scheduling related per-task fields: + */ +static int sched_show(struct seq_file *m, void *v) +{ + struct inode *inode = m->private; + struct task_struct *p; + + WARN_ON(!inode); + + p = get_proc_task(inode); + if (!p) + return -ESRCH; + proc_sched_show_task(p, m); + + put_task_struct(p); + + return 0; +} + +static ssize_t +sched_write(struct file *file, const char __user *buf, + size_t count, loff_t *offset) +{ + struct inode *inode = file->f_path.dentry->d_inode; + struct task_struct *p; + + WARN_ON(!inode); + + p = get_proc_task(inode); + if (!p) + return -ESRCH; + proc_sched_set_task(p); + + put_task_struct(p); + + return count; +} + +static int sched_open(struct inode *inode, struct file *filp) +{ + int ret; + + ret = single_open(filp, sched_show, NULL); + if (!ret) { + struct seq_file *m = filp->private_data; + + m->private = inode; + } + return ret; +} + +static const struct file_operations proc_pid_sched_operations = { + .open = sched_open, + .read = seq_read, + .write = sched_write, + .llseek = seq_lseek, + .release = seq_release, +}; + +#endif + static void *proc_pid_follow_link(struct dentry *dentry, struct nameidata *nd) { struct inode *inode = dentry->d_inode; @@ -1963,6 +2026,9 @@ static const struct pid_entry tgid_base_stuff[] = { INF("environ", S_IRUSR, pid_environ), INF("auxv", S_IRUSR, pid_auxv), INF("status", S_IRUGO, pid_status), +#ifdef CONFIG_SCHED_DEBUG + REG("sched", S_IRUGO|S_IWUSR, pid_sched), +#endif INF("cmdline", S_IRUGO, pid_cmdline), INF("stat", S_IRUGO, tgid_stat), INF("statm", S_IRUGO, pid_statm), @@ -2247,6 +2313,9 @@ static const struct pid_entry tid_base_stuff[] = { INF("environ", S_IRUSR, pid_environ), INF("auxv", S_IRUSR, pid_auxv), INF("status", S_IRUGO, pid_status), +#ifdef CONFIG_SCHED_DEBUG + REG("sched", S_IRUGO|S_IWUSR, pid_sched), +#endif INF("cmdline", S_IRUGO, pid_cmdline), INF("stat", S_IRUGO, tid_stat), INF("statm", S_IRUGO, pid_statm), diff --git a/include/linux/sched.h b/include/linux/sched.h index c9d65738bb7a..785ec8465bd3 100644 --- a/include/linux/sched.h +++ b/include/linux/sched.h @@ -132,6 +132,26 @@ extern unsigned long nr_active(void); extern unsigned long nr_iowait(void); extern unsigned long weighted_cpuload(const int cpu); +struct seq_file; +struct cfs_rq; +#ifdef CONFIG_SCHED_DEBUG +extern void proc_sched_show_task(struct task_struct *p, struct seq_file *m); +extern void proc_sched_set_task(struct task_struct *p); +extern void +print_cfs_rq(struct seq_file *m, int cpu, struct cfs_rq *cfs_rq, u64 now); +#else +static inline void +proc_sched_show_task(struct task_struct *p, struct seq_file *m) +{ +} +static inline void proc_sched_set_task(struct task_struct *p) +{ +} +static inline void +print_cfs_rq(struct seq_file *m, int cpu, struct cfs_rq *cfs_rq, u64 now) +{ +} +#endif /* * Task state bitmask. NOTE! These bits are also diff --git a/kernel/sched_debug.c b/kernel/sched_debug.c new file mode 100644 index 000000000000..1baf87cceb7c --- /dev/null +++ b/kernel/sched_debug.c @@ -0,0 +1,275 @@ +/* + * kernel/time/sched_debug.c + * + * Print the CFS rbtree + * + * Copyright(C) 2007, Red Hat, Inc., Ingo Molnar + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License version 2 as + * published by the Free Software Foundation. + */ + +#include +#include +#include +#include +#include + +/* + * This allows printing both to /proc/sched_debug and + * to the console + */ +#define SEQ_printf(m, x...) \ + do { \ + if (m) \ + seq_printf(m, x); \ + else \ + printk(x); \ + } while (0) + +static void +print_task(struct seq_file *m, struct rq *rq, struct task_struct *p, u64 now) +{ + if (rq->curr == p) + SEQ_printf(m, "R"); + else + SEQ_printf(m, " "); + + SEQ_printf(m, "%15s %5d %15Ld %13Ld %13Ld %9Ld %5d " + "%15Ld %15Ld %15Ld %15Ld %15Ld\n", + p->comm, p->pid, + (long long)p->se.fair_key, + (long long)(p->se.fair_key - rq->cfs.fair_clock), + (long long)p->se.wait_runtime, + (long long)(p->nvcsw + p->nivcsw), + p->prio, + (long long)p->se.sum_exec_runtime, + (long long)p->se.sum_wait_runtime, + (long long)p->se.sum_sleep_runtime, + (long long)p->se.wait_runtime_overruns, + (long long)p->se.wait_runtime_underruns); +} + +static void print_rq(struct seq_file *m, struct rq *rq, int rq_cpu, u64 now) +{ + struct task_struct *g, *p; + + SEQ_printf(m, + "\nrunnable tasks:\n" + " task PID tree-key delta waiting" + " switches prio" + " sum-exec sum-wait sum-sleep" + " wait-overrun wait-underrun\n" + "------------------------------------------------------------------" + "----------------" + "------------------------------------------------" + "--------------------------------\n"); + + read_lock_irq(&tasklist_lock); + + do_each_thread(g, p) { + if (!p->se.on_rq || task_cpu(p) != rq_cpu) + continue; + + print_task(m, rq, p, now); + } while_each_thread(g, p); + + read_unlock_irq(&tasklist_lock); +} + +static void +print_cfs_rq_runtime_sum(struct seq_file *m, int cpu, struct cfs_rq *cfs_rq) +{ + s64 wait_runtime_rq_sum = 0; + struct task_struct *p; + struct rb_node *curr; + unsigned long flags; + struct rq *rq = &per_cpu(runqueues, cpu); + + spin_lock_irqsave(&rq->lock, flags); + curr = first_fair(cfs_rq); + while (curr) { + p = rb_entry(curr, struct task_struct, se.run_node); + wait_runtime_rq_sum += p->se.wait_runtime; + + curr = rb_next(curr); + } + spin_unlock_irqrestore(&rq->lock, flags); + + SEQ_printf(m, " .%-30s: %Ld\n", "wait_runtime_rq_sum", + (long long)wait_runtime_rq_sum); +} + +void print_cfs_rq(struct seq_file *m, int cpu, struct cfs_rq *cfs_rq, u64 now) +{ + SEQ_printf(m, "\ncfs_rq %p\n", cfs_rq); + +#define P(x) \ + SEQ_printf(m, " .%-30s: %Ld\n", #x, (long long)(cfs_rq->x)) + + P(fair_clock); + P(exec_clock); + P(wait_runtime); + P(wait_runtime_overruns); + P(wait_runtime_underruns); + P(sleeper_bonus); +#undef P + + print_cfs_rq_runtime_sum(m, cpu, cfs_rq); +} + +static void print_cpu(struct seq_file *m, int cpu, u64 now) +{ + struct rq *rq = &per_cpu(runqueues, cpu); + +#ifdef CONFIG_X86 + { + unsigned int freq = cpu_khz ? : 1; + + SEQ_printf(m, "\ncpu#%d, %u.%03u MHz\n", + cpu, freq / 1000, (freq % 1000)); + } +#else + SEQ_printf(m, "\ncpu#%d\n", cpu); +#endif + +#define P(x) \ + SEQ_printf(m, " .%-30s: %Ld\n", #x, (long long)(rq->x)) + + P(nr_running); + SEQ_printf(m, " .%-30s: %lu\n", "load", + rq->ls.load.weight); + P(ls.delta_fair); + P(ls.delta_exec); + P(nr_switches); + P(nr_load_updates); + P(nr_uninterruptible); + SEQ_printf(m, " .%-30s: %lu\n", "jiffies", jiffies); + P(next_balance); + P(curr->pid); + P(clock); + P(prev_clock_raw); + P(clock_warps); + P(clock_overflows); + P(clock_unstable_events); + P(clock_max_delta); + P(cpu_load[0]); + P(cpu_load[1]); + P(cpu_load[2]); + P(cpu_load[3]); + P(cpu_load[4]); +#undef P + + print_cfs_stats(m, cpu, now); + + print_rq(m, rq, cpu, now); +} + +static int sched_debug_show(struct seq_file *m, void *v) +{ + u64 now = ktime_to_ns(ktime_get()); + int cpu; + + SEQ_printf(m, "Sched Debug Version: v0.04, cfs-v20, %s %.*s\n", + init_utsname()->release, + (int)strcspn(init_utsname()->version, " "), + init_utsname()->version); + + SEQ_printf(m, "now at %Lu nsecs\n", (unsigned long long)now); + + for_each_online_cpu(cpu) + print_cpu(m, cpu, now); + + SEQ_printf(m, "\n"); + + return 0; +} + +void sysrq_sched_debug_show(void) +{ + sched_debug_show(NULL, NULL); +} + +static int sched_debug_open(struct inode *inode, struct file *filp) +{ + return single_open(filp, sched_debug_show, NULL); +} + +static struct file_operations sched_debug_fops = { + .open = sched_debug_open, + .read = seq_read, + .llseek = seq_lseek, + .release = seq_release, +}; + +static int __init init_sched_debug_procfs(void) +{ + struct proc_dir_entry *pe; + + pe = create_proc_entry("sched_debug", 0644, NULL); + if (!pe) + return -ENOMEM; + + pe->proc_fops = &sched_debug_fops; + + return 0; +} + +__initcall(init_sched_debug_procfs); + +void proc_sched_show_task(struct task_struct *p, struct seq_file *m) +{ + unsigned long flags; + int num_threads = 1; + + rcu_read_lock(); + if (lock_task_sighand(p, &flags)) { + num_threads = atomic_read(&p->signal->count); + unlock_task_sighand(p, &flags); + } + rcu_read_unlock(); + + SEQ_printf(m, "%s (%d, #threads: %d)\n", p->comm, p->pid, num_threads); + SEQ_printf(m, "----------------------------------------------\n"); +#define P(F) \ + SEQ_printf(m, "%-25s:%20Ld\n", #F, (long long)p->F) + + P(se.wait_start); + P(se.wait_start_fair); + P(se.exec_start); + P(se.sleep_start); + P(se.sleep_start_fair); + P(se.block_start); + P(se.sleep_max); + P(se.block_max); + P(se.exec_max); + P(se.wait_max); + P(se.wait_runtime); + P(se.wait_runtime_overruns); + P(se.wait_runtime_underruns); + P(se.sum_wait_runtime); + P(se.sum_exec_runtime); + SEQ_printf(m, "%-25s:%20Ld\n", + "nr_switches", (long long)(p->nvcsw + p->nivcsw)); + P(se.load.weight); + P(policy); + P(prio); +#undef P + + { + u64 t0, t1; + + t0 = sched_clock(); + t1 = sched_clock(); + SEQ_printf(m, "%-25s:%20Ld\n", + "clock-delta", (long long)(t1-t0)); + } +} + +void proc_sched_set_task(struct task_struct *p) +{ + p->se.sleep_max = p->se.block_max = p->se.exec_max = p->se.wait_max = 0; + p->se.wait_runtime_overruns = p->se.wait_runtime_underruns = 0; + p->se.sum_exec_runtime = 0; +} -- cgit v1.2.3 From 6fb43d7b50e49a36f8be3199141bec473e5ecb00 Mon Sep 17 00:00:00 2001 From: Ingo Molnar Date: Mon, 9 Jul 2007 18:52:01 +0200 Subject: sched: micro-optimize mmdrop() micro-optimize mmdrop(). Improves schedule()'s assembly a bit. Signed-off-by: Ingo Molnar --- include/linux/sched.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'include/linux/sched.h') diff --git a/include/linux/sched.h b/include/linux/sched.h index 785ec8465bd3..cfb680585ab8 100644 --- a/include/linux/sched.h +++ b/include/linux/sched.h @@ -1514,7 +1514,7 @@ extern struct mm_struct * mm_alloc(void); extern void FASTCALL(__mmdrop(struct mm_struct *)); static inline void mmdrop(struct mm_struct * mm) { - if (atomic_dec_and_test(&mm->mm_count)) + if (unlikely(atomic_dec_and_test(&mm->mm_count))) __mmdrop(mm); } -- cgit v1.2.3