build sched domains tracking cpusets

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.

Signed-off-by John Hawkes <[email protected]>

Index: linux/include/linux/sched.h
===================================================================

+static int find_existing_sched_domain(int cpu, const cpumask_t *cpu_map)

include/linux/sched.h +20 -0

+{
+	int sd_idx;
+
+	for (sd_idx = 0; sd_idx < SCHED_DOMAIN_CPUSET_MAX; sd_idx++) {
+		struct sched_domain_bundle *sd_cpuset_bundle;
+		struct sched_domain *sd;
+
+		if (!test_bit(sd_idx, &per_cpu(sd_cpusets_used, cpu)))
+			continue;
+		sd_cpuset_bundle = &per_cpu(sd_cpusets_bundle[sd_idx], cpu);
+		sd = &sd_cpuset_bundle->sd_cpuset;
+		if (cpus_equal(*cpu_map, sd->span))
+			return sd_idx;
+	}
+
+	return SCHED_DOMAIN_CPUSET_MAX;
+}
+
+void add_sched_domain(const cpumask_t *cpu_map)
+{

Index: linux/kernel/cpuset.c
===================================================================

kernel/cpuset.c +6 -2

@@ -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;
 }
 

include/linux/sched.h enum idle_type · line 561

Quoted 5 lines

include/linux/sched.h +1 -0

@@ -558,6 +558,7 @@ enum idle_type
 #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_TRACKS_CPUSET 4096 /* Spam matches non-exclusive cpuset */

I'd just use the next bit, and we should convert these to hex as well I guess... I don't know what I was thinking ;)

include/linux/sched.h struct sched_domain { · line 634

Quoted 7 lines

include/linux/sched.h +1 -0

 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);

Not a big deal, but I'd probably be happier with a single hook from the cpusets code, which does the right thing depending on whether it is exclusive or not.

Hard to know which way around the layering should go, but I think that it is simply a hint to the balancer code to do something nice, and as such we should leave it completely to the scheduler.

Review struct sched_domain { · line 635

Quoted 1 line

(quoted diff) +1 -0

+#ifdef CONFIG_CPUSETS

CPUSETS only? Or do we want to try to help sched_setaffinity users as well?

kernel/sched.c next_sg: · line 5801

Quoted 5 lines

kernel/sched.c +5 -0

+struct sched_domain_bundle {
+ struct sched_domain sd_cpuset;
+ struct sched_group **sg_cpuset_nodes;
+ int use_count;
+};

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 6 lines

(quoted diff) +2 -0

+#define SCHED_DOMAIN_CPUSET_MAX 8 /* power of 2 */
+static DEFINE_PER_CPU(long, sd_cpusets_used) = { 1UL 

<<SCHED_DOMAIN_CPUSET_MAX};
+static DEFINE_PER_CPU(struct
sched_domain_bundle[SCHED_DOMAIN_CPUSET_MAX],
+ sd_cpusets_bundle);

Do we need a limit of 8? If you're worried about memory, I guess there are lots of ways to DOS the system... if you're worried about scheduler balancing overhead, we could do a seperate traversal of these guys at a reduced interval (I guess that still leaves some places needing help, though)

Quoted 1 line

+static int find_existing_sched_domain(int cpu, const cpumask_t *cpu_map)

Probably some way to distinguish these guys as operating on your "bundle" stack would make it a bit clearer?

Quoted 6 lines

+ /* tweak sched_domain params based upon domain size */
+ *sd = SD_NODE_INIT;
+ sd->flags |= SD_TRACKS_CPUSET;
+ sd->max_interval = 8*(min(new_sd_span, 32));
+ sd->span = *cpu_map;
+ cpu_set(cpu, new_sd_cpu_map);

Can we just have a new SD_xxx_INIT for these?

Quoted 25 lines

Index: linux/kernel/cpuset.c
===================================================================

kernel/cpuset.c 2006-07-05 16:01:14.892039725 -0700 renamed from kernel/cpuset.c 2006-07-05 15:51:38.873939805 -0700 +6 -2

@@ -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 */

Quoted 3 lines

spin_lock(&cs->dentry->d_lock);
d = dget(cs->dentry);

So you're just doing the inside. What about the complement? That way you'd get a nice symmetric allocation on all cpus for each cpuset... but that probably would require making the limit greater than 8.

And it would be probably required for good sched_setaffinity balancing too.