CINXE.COM

<?xml version="1.0" encoding="UTF-8" standalone="yes"?> <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>LKML: hawkes@sgi ...: [PATCH] -mm tree: broken "dynamic sched domains" and "migration cost"</title><link href="/css/message.css" rel="stylesheet" type="text/css" /><link href="/css/wrap.css" rel="alternate stylesheet" type="text/css" title="wrap" /><link href="/css/nowrap.css" rel="stylesheet" type="text/css" title="nowrap" /><link href="/favicon.ico" rel="shortcut icon" /><script src="/js/simple-calendar.js" type="text/javascript"></script><script src="/js/styleswitcher.js" type="text/javascript"></script><link rel="alternate" type="application/rss+xml" title="lkml.org : last 100 messages" href="/rss.php" /><link rel="alternate" type="application/rss+xml" title="lkml.org : last messages by 	hawkes@sgi ..." href="/groupie.php?aid=4069" /><script> var _paq = window._paq = window._paq || []; /* tracker methods like "setCustomDimension" should be called before "trackPageView" */ _paq.push(["setDoNotTrack", true]); _paq.push(["disableCookies"]); _paq.push(['trackPageView']); _paq.push(['enableLinkTracking']); (function() { var u="//m.lkml.org/"; _paq.push(['setTrackerUrl', u+'matomo.php']); _paq.push(['setSiteId', '1']); var d=document, g=d.createElement('script'), s=d.getElementsByTagName('script')[0]; g.async=true; g.src=u+'matomo.js'; s.parentNode.insertBefore(g,s); })(); </script></head><body onload="es.jasper.simpleCalendar.init();" itemscope="itemscope" itemtype="http://schema.org/BlogPosting"><table border="0" cellpadding="0" cellspacing="0"><tr><td width="180" align="center"><a href="/"><img style="border:0;width:135px;height:32px" src="/images/toprowlk.gif" alt="lkml.org" /></a></td><td width="32">聽</td><td class="nb"><div><a class="nb" href="/lkml"> [lkml]</a> 聽 <a class="nb" href="/lkml/2005"> [2005]</a> 聽 <a class="nb" href="/lkml/2005/12"> [Dec]</a> 聽 <a class="nb" href="/lkml/2005/12/9"> [9]</a> 聽 <a class="nb" href="/lkml/last100"> [last100]</a> 聽 <a href="/rss.php"><img src="/images/rss-or.gif" border="0" alt="RSS Feed" /></a></div><div>Views: <a href="#" class="nowrap" onclick="setActiveStyleSheet('wrap');return false;">[wrap]</a><a href="#" class="wrap" onclick="setActiveStyleSheet('nowrap');return false;">[no wrap]</a> 聽 <a class="nb" href="/lkml/mheaders/2005/12/9/202" onclick="this.href='/lkml/headers'+'/2005/12/9/202';">[headers]</a>聽 <a href="/lkml/bounce/2005/12/9/202">[forward]</a>聽 </div></td><td width="32">聽</td></tr><tr><td valign="top"><div class="es-jasper-simpleCalendar" baseurl="/lkml/"></div><div class="threadlist">Messages in this thread</div><ul class="threadlist"><li class="root"><a href="/lkml/2005/12/9/202">First message in thread</a></li><li class="origin"><a href="/lkml/2005/12/9/255"> hawkes@sgi ...</a><ul><li><a href="/lkml/2005/12/9/255">Paul Jackson</a></li><li><a href="/lkml/2005/12/10/58">Ingo Molnar</a></li><li><a href="/lkml/2005/12/10/60">Ingo Molnar</a><ul><li><a href="/lkml/2005/12/12/192">"John Hawkes"</a><ul><li><a href="/lkml/2005/12/13/26">Ingo Molnar</a></li></ul></li></ul></li></ul></li></ul><div class="threadlist">Patch in this message</div><ul class="threadlist"><li><a href="/lkml/diff/2005/12/9/202/1">Get diff 1</a></li></ul></td><td width="32" rowspan="2" class="c" valign="top"><img src="/images/icornerl.gif" width="32" height="32" alt="/" /></td><td class="c" rowspan="2" valign="top" style="padding-top: 1em"><table><tr><td><table><tr><td class="lp">Date</td><td class="rp" itemprop="datePublished">Fri, 9 Dec 2005 12:54:54 -0800 (PST)</td></tr><tr><td class="lp">From</td><td class="rp" itemprop="author"> hawkes@sgi ...</td></tr><tr><td class="lp">Subject</td><td class="rp" itemprop="name">[PATCH] -mm tree: broken "dynamic sched domains" and "migration cost"</td></tr></table></td><td></td></tr></table><pre itemprop="articleBody">As recently as 2.6.15-rc5-mm1 the combination of "migration cost matrix" calculations and "dynamic sched domains" is broken. This patch fixes the basic bug, even though I still have larger problems with the "migration cost matrix" concept as implemented. The essence of the bug is that the code and data in the CPU Scheduler that perform the cost calculation are declared as "__initdata" or "__init" or "__devinit", even though a runtime declaration of a cpu-exclusive cpuset will invoke build_sched_domains() to rebuilt the sched domains, and that calls the now-released calibrate_migration_costs(), et al. The attached patch changes the declarations of the code and data to make them persistent. To review, to create a cpu-exclusive cpuset, do something like this: cd /dev/cpuset mkdir cpu0 echo 0 > cpu0/cpus echo 0 > cpu0/mems echo 1 > cpu0/cpu_exclusive Various other problems with "migration cost matrix" are not addressed by this patch. They are: (1) calibrate_migration_costs() printk's the matrix at boot time, and for large NR_CPUS values this can be voluminous. We might consider changing the naked printk()'s into printk(KERN_DEBUG ...) to hide them to everyone but a sysadmin or developer who has a need to view the values. (2) calibrate_migration_costs() printk's the matrix for every call to build_sched_domains(), which is called twice for each declaration of a cpu-exclusive cpuset. The syslog output is voluminous for large NR_CPUS values. It is unclear to me how interesting this output is after the initial display at boot time. Various Job Manager software will actively create and destroy cpu-exclusive cpusets, and that will flood the syslog with matrix output. (3) For a cpu-exclusive cpuset cpu, the domain_distance() calculation produces a legal value, but not a useful value. That is to say, if cpu0 is isolated into a cpu-exclusive cpuset, then the semantic meaning of "domain distance" between cpu0 and another CPU outside of this cpu-exclusive is essentially undefined. No load-balancing will occur in or out of this cpu-exclusive cpuset. There is no need to measure_migration_cost() of any migrations in or out of a cpu-exclusive cpuset. The reason why this is significant is that measure_migration_cost() is expensive, and the creation of that cpu0 cpu-exclusive cpuset stalls the echo 1 > cpu0/cpu_exclusive about six seconds on a 64p ia64/sn2 platform, all to calculate a cost value that is never used. (4) The expense of the migration_cost() calculation can be sizeable. It can be reduced somewhat by changing the 5% increments into 10% or even higher. That reduces the boot-time "calibration delay" from 50 seconds down to 20 seconds (for the 64p ia64/sn2) for three levels of sched domains, and the declaration of a single cpu0 cpu-exclusive dynamic sched domain from 6 seconds down to 5 (all to calculate that unnecessary new domain_distance). (5) Besides, the migration cost between any two CPUs is something that can be calculated once at boot time and remembered thereafter. I suspect the reason why the algorithm doesn't do this is that an exhaustive NxN calculation will be very slow for large NR_CPUS counts, which explains why the calculations are now done in the context of sched domains. However, simply calculating the migration cost for each "domain distance" presupposes that the sched domain groupings accurately reflect true migration costs. For platforms like the ia64/sn2 this is not true. For example, a 64p ia64/sn2 will have three sched domain levels: level zero is each 2-CPU pair within a node; level one is an SD_NODES_PER_DOMAIN-size arbitrary clump of 32 CPUs; level two is all 64 CPUs. Looking at that middle level, if I understand the algorithm, there is one and only one migration_cost[1] calculation made for an arbitrary choice of one CPU in a 32-CPU clump and another CPU in that clump. Reality is that there are various migration costs for different pairs of CPUs in that set of 32. This is yet another reason why I believe we don't need to do those 5% size increments to get really accurate timings. For now, here is the patch to avoid the basic bug: Signed-off-by: John Hawkes <hawkes@sgi.com> Index: linux/kernel/sched.c =================================================================== --- linux.orig/kernel/sched.c 2005-12-09 09:26:04.000000000 -0800 +++ linux/kernel/sched.c 2005-12-09 10:53:28.000000000 -0800 @@ -5295,7 +5295,7 @@ #define MIGRATION_FACTOR_SCALE 128 -static __initdata unsigned int migration_factor = MIGRATION_FACTOR_SCALE; +static unsigned int migration_factor = MIGRATION_FACTOR_SCALE; static int __init setup_migration_factor(char *str) { @@ -5310,7 +5310,7 @@ * 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: */ -__devinit static unsigned long domain_distance(int cpu1, int cpu2) +static unsigned long domain_distance(int cpu1, int cpu2) { unsigned long distance = 0; struct sched_domain *sd; @@ -5329,7 +5329,7 @@ return distance; } -static __initdata unsigned int migration_debug; +static unsigned int migration_debug; static int __init setup_migration_debug(char *str) { @@ -5345,7 +5345,7 @@ * bootup. Gets used in the domain-setup code (i.e. during SMP * bootup). */ -__initdata unsigned int max_cache_size; +unsigned int max_cache_size; static int __init setup_max_cache_size(char *str) { @@ -5360,7 +5360,7 @@ * is the operation that is timed, so we try to generate unpredictable * cachemisses that still end up filling the L2 cache: */ -__init static void touch_cache(void *__cache, unsigned long __size) +static void touch_cache(void *__cache, unsigned long __size) { unsigned long size = __size/sizeof(long), chunk1 = size/3, chunk2 = 2*size/3; @@ -5382,8 +5382,8 @@ /* * Measure the cache-cost of one task migration. Returns in units of nsec. */ -__init static unsigned long long measure_one(void *cache, unsigned long size, - int source, int target) +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; @@ -5449,7 +5449,7 @@ * Architectures can prime the upper limit of the search range via * max_cache_size, otherwise the search range defaults to 20MB...64K. */ -__init static unsigned long long +static unsigned long long measure_cost(int cpu1, int cpu2, void *cache, unsigned int size) { unsigned long long cost1, cost2; @@ -5501,7 +5501,7 @@ return cost1 - cost2; } -__devinit static unsigned long long measure_migration_cost(int cpu1, int cpu2) +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; @@ -5606,7 +5606,7 @@ return 2 * max_cost * migration_factor / MIGRATION_FACTOR_SCALE; } -void __devinit calibrate_migration_costs(void) +void calibrate_migration_costs(void) { int cpu1 = -1, cpu2 = -1, cpu, orig_cpu = raw_smp_processor_id(); struct sched_domain *sd; - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at <a href="http://vger.kernel.org/majordomo-info.html">http://vger.kernel.org/majordomo-info.html</a> Please read the FAQ at <a href="http://www.tux.org/lkml/">http://www.tux.org/lkml/</a> </pre></td><td width="32" rowspan="2" class="c" valign="top"><img src="/images/icornerr.gif" width="32" height="32" alt="\" /></td></tr><tr><td align="right" valign="bottom"> 聽 </td></tr><tr><td align="right" valign="bottom">聽</td><td class="c" valign="bottom" style="padding-bottom: 0px"><img src="/images/bcornerl.gif" width="32" height="32" alt="\" /></td><td class="c">聽</td><td class="c" valign="bottom" style="padding-bottom: 0px"><img src="/images/bcornerr.gif" width="32" height="32" alt="/" /></td></tr><tr><td align="right" valign="top" colspan="2"> 聽 </td><td class="lm">Last update: 2005-12-09 21:58 聽聽 [from the cache] 漏2003-2020 <a href="http://blog.jasper.es/">Jasper Spaans</a>|hosted at <a href="https://www.digitalocean.com/?refcode=9a8e99d24cf9">Digital Ocean</a> and my Meterkast|<a href="http://blog.jasper.es/categories.html#lkml-ref">Read the blog</a></td><td>聽</td></tr></table><script language="javascript" src="/js/styleswitcher.js" type="text/javascript"></script></body></html>