cpusets/sched_domain reconciliation

This patch reconciles cpusets and sched_domains that get out of sync due to disabling and re-enabling cpu's.

This is still a problem in the 2.6.23-rc3 kernel. (and also 2.6.22)

Here is an example of how the problem can occur:

system of cpu's 0 1 2 3 4 5
create cpuset /x 2 3 4 5
create cpuset /x/y 2 3
all cpusets are cpu_exclusive

disable cpu 3
x is now 2 4 5
x/y is now 2
enable cpu 3
cpusets x and x/y are unchanged

to restore the cpusets:

     echo 2-5 > /dev/cpuset/x
     echo 2-3 > /dev/cpuset/x/y

At the first echo, which restores 3 to cpuset x, update_cpu_domains() is called for cpuset x/.
system of cpu's 0 1 2 3 4 5
x is now 2 3 4 5
x/y is now 2

The system is partitioned between:

	its parent, the root cpuset, minus its child (x/ is 2-5): 0-1
        and x/ (2-5) , minus its child (x/y/ 2): 3-5

The sched_domain's for parent 0-1 are updated. The sched_domain's for current 3-5 are updated.

But 2 has been untouched.
As a result, 3's SD points to sched_group_phys[3] which is the only sched_group_phys on 3's list. It points to itself.
But 2's SD points to sched_group_phys[2], which still points to sched_group_phys[3].
When cpu 2 executes find_busiest_group() it will hang on the non- circular sched_group list.

cpuset.c:

This solution is to update the sched_domain's for the cpuset whose cpu's were changed and, in addition, all its children. Instead of calling update_cpu_domains(), call update_cpu_domains_tree(), which calls update_cpu_domains() for every node from the one specified down to all its children.

The extra sched_domain reconstruction is overhead, but only at the frequency of administrative change to the cpusets.

There seems to be no administrative procedural work-around. In the example above one could not reverse the two echo's and set x/y before x/. It is not logical, so not allowed (Permission denied).

Thus the patch to cpuset.c makes the sched_domain's correct.

sched.c:

The patch to sched.c prevents the cpu hangs that otherwise occur until the sched_domain's are made correct.

It puts checks into find_busiest_group() and find_idlest_group() that break from their loops on a sched_group that points to itself. This is needed because cpu's are going through load balancing before all sched_domains have been reconstructed (see the example above).

This is admittedly a kludge. I leave it to the scheduler gurus to recommend a better way to keep cpus out of the sched_domains while they are being reconstructed.

Diffed against 2.6.23-rc3

---
 kernel/cpuset.c |   43 +++++++++++++++++++++++++++++++++++++++----
 kernel/sched.c  |   18 ++++++++++++++----
 2 files changed, 53 insertions(+), 8 deletions(-)

Index: linus.070821/kernel/sched.c
===================================================================
@@ -1196,11 +1196,14 @@ static inline unsigned long cpu_avg_load
 static struct sched_group *
 find_idlest_group(struct sched_domain *sd, struct task_struct *p, int this_cpu)
 {
-	struct sched_group *idlest = NULL, *this = NULL, *group = sd->groups;
+	struct sched_group *idlest = NULL, *this = sd->groups, *group = sd->groups;
+	struct sched_group *self, *prev;
 	unsigned long min_load = ULONG_MAX, this_load = 0;
 	int load_idx = sd->forkexec_idx;
 	int imbalance = 100 + (sd->imbalance_pct-100)/2;
 
+	prev = group;
+	self = group;
 	do {
 		unsigned long load, avg_load;
 		int local_group;

@@ -1237,8 +1240,10 @@ find_idlest_group(struct sched_domain *s
 			idlest = group;
 		}
 nextgroup:
+		prev = self;
+		self = group;
 		group = group->next;
-	} while (group != sd->groups);
+	} while (group != sd->groups && group != self && group != prev);
 
 	if (!idlest || 100*this_load < imbalance*min_load)
 		return NULL;

@@ -2288,7 +2293,8 @@ find_busiest_group(struct sched_domain *
 		   unsigned long *imbalance, enum cpu_idle_type idle,
 		   int *sd_idle, cpumask_t *cpus, int *balance)
 {
-	struct sched_group *busiest = NULL, *this = NULL, *group = sd->groups;
+	struct sched_group *busiest = NULL, *this = sd->groups, *group = sd->groups;
+	struct sched_group *self, *prev;
 	unsigned long max_load, avg_load, total_load, this_load, total_pwr;
 	unsigned long max_pull;
 	unsigned long busiest_load_per_task, busiest_nr_running;

@@ -2311,6 +2317,8 @@ find_busiest_group(struct sched_domain *
 	else
 		load_idx = sd->idle_idx;
 
+	prev = group;
+	self = group;
 	do {
 		unsigned long load, group_capacity;
 		int local_group;

@@ -2443,8 +2451,10 @@ find_busiest_group(struct sched_domain *
 		}
 group_next:
 #endif
+		prev = self;
+		self = group;
 		group = group->next;
-	} while (group != sd->groups);
+	} while (group != sd->groups && group != self && group != prev);
 
 	if (!busiest || this_load >= max_load || busiest_nr_running == 0)
 		goto out_balanced;

Cliff Wickman
Silicon Graphics, Inc.
[email protected]
(651) 683-3824

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>