Skip to contentSkip to conversation

build sched domains tracking cpusets

PATCH [email protected] 2 participants 2 messages Jul 7, 2006 – Jul 10, 2006 Scheduler

lore
Share & tools
lore
#0 lore raw

Version #2, incorporating some of Nick Piggin's feedback. Still only defined for CONFIG_CPUSETS.

Moderate-to-large single system image systems are often carved up into dynamic cpusets, and applications are individually assigned to specific cpusets. The current CPU scheduler's find_busiest_cpu() load-balancing doesn't work well in this environment, as the busiest CPU may be busy with tasks that cannot migrate out of their constrained cpuset (because of the task->cpus_allowed), and this effectively stymies any passive load-balancing attempted by a CPU not in this busiest CPU's cpuset. This disabling of load-balancing has been observed by several SGI customers and can be a serious performance problem.

A lesser observed issue is inefficient load-balancing within (for example) a cpuset that spans one of those 16-node sched domains that are built for large NUMA systems. The next broader sched domain is the all-CPUs domain, which load-balances across the 16-node sched domain boundaries relatively infrequently.

This patch introduces the notion of dynamic sched domains (and sched groups) that track the creation and deletion of cpusets. Up to eight of these dynamic sched domains can exist per CPU, which seems to handle the observed use of cpusets by one popular job manager. Essentially, every new cpuset causes the creation of a new sched domain for the CPUs of that cpuset, and a deletion of the cpuset causes the destruction of that dynamic sched domain. New sched domains are inserted into each CPU's list as appropriate. The limit of 8/CPU (vs. unlimited) not only caps the upperbound of kmalloc memory being assigned to sched domain and sched group structs (thereby avoiding a potential denial-of-service attack by a runaway user creating cpusets), but it also caps the number of sched domains being searched by various algorithms in the scheduler.

A "feature" of this implementation is that these dynamic sched domains build up until that limit of 8/CPU is reached, at which point no additional sched domains are created; or until a cpu-exclusive cpuset gets declared, at which point all the dynamically created sched domains in the affected CPUs get destroyed. A more sophisticated algorithm in kernel/cpuset.c could redeclare the dynamic sched domains after a cpu-exclusive cpuset gets declared, but that is outside the scope of this simple patch's simple change to kernel/cpuset.c.

include/linux/sched.h +12 -8
Index: linux/include/linux/sched.h
===================================================================
@@ -550,14 +550,15 @@ enum idle_type
 #ifdef CONFIG_SMP
 #define SCHED_LOAD_SCALE	128UL	/* increase resolution of load */
 
-#define SD_LOAD_BALANCE		1	/* Do load balancing on this domain. */
-#define SD_BALANCE_NEWIDLE	2	/* Balance when about to become idle */
-#define SD_BALANCE_EXEC		4	/* Balance on exec */
-#define SD_BALANCE_FORK		8	/* Balance on fork, clone */
-#define SD_WAKE_IDLE		16	/* Wake to idle CPU on task wakeup */
-#define SD_WAKE_AFFINE		32	/* Wake task to waking CPU */
-#define SD_WAKE_BALANCE		64	/* Perform balancing at task wakeup */
-#define SD_SHARE_CPUPOWER	128	/* Domain members share cpu power */
+#define SD_LOAD_BALANCE		0x00000001	/* Do load balancing */
+#define SD_BALANCE_NEWIDLE	0x00000002	/* Balance when becoming idle */
+#define SD_BALANCE_EXEC		0x00000004	/* Balance on exec */
+#define SD_BALANCE_FORK		0x00000008	/* Balance on fork, clone */
+#define SD_WAKE_IDLE		0x00000010	/* Balance to idle CPU on wakeup */
+#define SD_WAKE_AFFINE		0x00000020	/* Wake task to waking CPU */
+#define SD_WAKE_BALANCE		0x00000040	/* Balance at task wakeup */
+#define SD_SHARE_CPUPOWER	0x00000080	/* Domain members share cpu power */
+#define SD_TRACKS_CPUSET	0x00000100	/* Span matches non-exclusive cpuset */
 
 struct sched_group {
 	struct sched_group *next;	/* Must be a circular list */
@@ -630,6 +631,9 @@ struct sched_domain {
 extern void partition_sched_domains(cpumask_t *partition1,
 				    cpumask_t *partition2);
 
+extern void add_sched_domain(const cpumask_t *cpu_map);
+extern void destroy_sched_domain(const cpumask_t *cpu_map);
+
 /*
  * Maximum cache size the migration-costs auto-tuning code will
  * search from:
kernel/sched.c +361 -101

545 lines not on this page · raw message

include/linux/topology.h +28 -0
Index: linux/include/linux/topology.h
===================================================================
@@ -141,6 +141,34 @@
 }
 #endif
 
+/* Common values for Cpusets domain */
+#ifndef SD_CPUSET_INIT
+#define SD_CPUSET_INIT (struct sched_domain) {		\
+	.span			= CPU_MASK_NONE,	\
+	.parent			= NULL,			\
+	.groups			= NULL,			\
+	.min_interval		= 8,			\
+	.max_interval		= 8*(min(num_online_cpus(), 32)), \
+	.busy_factor		= 64,			\
+	.imbalance_pct		= 125,			\
+	.cache_nice_tries	= 2,			\
+	.busy_idx		= 3,			\
+	.idle_idx		= 2,			\
+	.newidle_idx		= 0, /* unused */	\
+	.wake_idx		= 1,			\
+	.forkexec_idx		= 1,			\
+	.per_cpu_gain		= 100,			\
+	.flags			= SD_TRACKS_CPUSET	\
+				| SD_LOAD_BALANCE	\
+				| SD_BALANCE_EXEC	\
+				| SD_BALANCE_FORK	\
+				| SD_WAKE_BALANCE,	\
+	.last_balance		= jiffies,		\
+	.balance_interval	= 64,			\
+	.nr_balance_failed	= 0,			\
+}
+#endif
+
 /* sched_domains SD_ALLNODES_INIT for NUMA machines */
 #define SD_ALLNODES_INIT (struct sched_domain) {	\
 	.span			= CPU_MASK_NONE,	\
kernel/cpuset.c +8 -2
Index: linux/kernel/cpuset.c
===================================================================
@@ -828,8 +828,12 @@ static int update_cpumask(struct cpuset 
 	mutex_lock(&callback_mutex);
 	cs->cpus_allowed = trialcs.cpus_allowed;
 	mutex_unlock(&callback_mutex);
-	if (is_cpu_exclusive(cs) && !cpus_unchanged)
-		update_cpu_domains(cs);
+	if (!cpus_unchanged) {
+		if (is_cpu_exclusive(cs))
+			update_cpu_domains(cs);
+		else
+			add_sched_domain(&cs->cpus_allowed);
+	}
 	return 0;
 }
 
@@ -1934,6 +1938,8 @@ static int cpuset_rmdir(struct inode *un
 	set_bit(CS_REMOVED, &cs->flags);
 	if (is_cpu_exclusive(cs))
 		update_cpu_domains(cs);
+	else
+		destroy_sched_domain(&cs->cpus_allowed);
 	list_del(&cs->sibling);	/* delete my sibling from parent->children */
 	spin_lock(&cs->dentry->d_lock);
 	d = dget(cs->dentry);
#1 lore raw
Quoted 6 lines · On Fri, Jul 07, 2006 at 12:31:07PM -0700, [email protected] wrote:

From: "Nick Piggin" <[email protected]>

Quoted 4 lines

Can you get away without using the bundle? Or does it make things easier? You could add a new use_count to struct sched_domain if you'd like.... does it make the setup/teardown too difficult?

Quoted 7 lines

The use_count is a ploy to reduce the demand for SCHED_DOMAIN_CPUSET_MAX
slots. I have been told that one popular job manager will create some duplicate cpusets.

The bundle is really there to simplify discovering the sched group lists.

I think we can do away with the bundle. sd has a pointer to the sched_group and the first cpu in sd->span can free the groups list allocation.

thanks,
suresh