cpuset and sched domains: sched_load_balance flag

From: Paul Jackson <[email protected]>

Add a new per-cpuset flag called 'sched_load_balance'.

When enabled in a cpuset (the default value) it tells the kernel scheduler that the scheduler should provide the normal load balancing on the CPUs in that cpuset, sometimes moving tasks from one CPU to a second CPU if the second CPU is less loaded and if that task is allowed to run there.

When disabled (write "0" to the file) then it tells the kernel scheduler that load balancing is not required for the CPUs in that cpuset.

Now even if this flag is disabled for some cpuset, the kernel may still have to load balance some or all the CPUs in that cpuset, if some overlapping cpuset has its sched_load_balance flag enabled.

If there are some CPUs that are not in any cpuset whose sched_load_balance flag is enabled, the kernel scheduler will not load balance tasks to those CPUs.

Moreover the kernel will partition the 'sched domains' (non-overlapping sets of CPUs over which load balancing is attempted) into the finest granularity partition that it can find, while still keeping any two CPUs that are in the same shed_load_balance enabled cpuset in the same element of the partition.

This serves two purposes:
1) It provides a mechanism for real time isolation of some CPUs, and
2) it can be used to improve performance on systems with many CPUs by supporting configurations in which load balancing is not done across all CPUs at once, but rather only done in several smaller disjoint sets of CPUs.

This mechanism replaces the earlier overloading of the per-cpuset flag 'cpu_exclusive', which overloading was removed in an earlier
patch: cpuset-remove-sched-domain-hooks-from-cpusets

See further the Documentation and comments in the code itself.

---

Andrew - this patch goes right after your *-mm patch:
task-containers-enable-containers-by-default-in-some-configs.patch
and before "add-containerstats-v3.patch"

 Documentation/cpusets.txt |  141 +++++++++++++++++++++++++
 include/linux/sched.h     |    2 
 kernel/cpuset.c           |  254 +++++++++++++++++++++++++++++++++++++++++++++-
 kernel/sched.c            |   72 ++++++++++---
 4 files changed, 450 insertions(+), 19 deletions(-)

@@ -19,7 +19,8 @@ CONTENTS:
   1.4 What are exclusive cpusets ?
   1.5 What is memory_pressure ?
   1.6 What is memory spread ?
-  1.7 How do I use cpusets ?
+  1.7 What is sched_load_balance ?
+  1.8 How do I use cpusets ?
 2. Usage Examples and Syntax
   2.1 Basic Usage
   2.2 Adding/removing cpus

@@ -359,8 +360,144 @@ policy, especially for jobs that might h
 data set, the memory allocation across the nodes in the jobs cpuset
 can become very uneven.
 
+1.7 What is sched_load_balance ?
+--------------------------------
+
+The kernel scheduler (kernel/sched.c) automatically load balances
+tasks.  If one CPU is underutilized, kernel code running on that
+CPU will look for tasks on other more overloaded CPUs and move those
+tasks to itself, within the constraints of such placement mechanisms
+as cpusets and sched_setaffinity.
+
+The algorithmic cost of load balancing and its impact on key shared
+kernel data structures such as the task list increases more than
+linearly with the number of CPUs being balanced.  So the scheduler
+has support to  partition the systems CPUs into a number of sched
+domains such that it only load balances within each sched domain.
+Each sched domain covers some subset of the CPUs in the system;
+no two sched domains overlap; some CPUs might not be in any sched
+domain and hence won't be load balanced.
+
+Put simply, it costs less to balance between two smaller sched domains
+than one big one, but doing so means that overloads in one of the
+two domains won't be load balanced to the other one.
+
+By default, there is one sched domain covering all CPUs, except those
+marked isolated using the kernel boot time "isolcpus=" argument.
+
+This default load balancing across all CPUs is not well suited for
+the following two situations:
+ 1) On large systems, load balancing across many CPUs is expensive.
+    If the system is managed using cpusets to place independent jobs
+    on separate sets of CPUs, full load balancing is unnecessary.
+ 2) Systems supporting realtime on some CPUs need to minimize
+    system overhead on those CPUs, including avoiding task load
+    balancing if that is not needed.
+
+When the per-cpuset flag "sched_load_balance" is enabled (the default
+setting), it requests that all the CPUs in that cpusets allowed 'cpus'
+be contained in a single sched domain, ensuring that load balancing
+can move a task (not otherwised pinned, as by sched_setaffinity)
+from any CPU in that cpuset to any other.
+
+When the per-cpuset flag "sched_load_balance" is disabled, then the
+scheduler will avoid load balancing across the CPUs in that cpuset,
+--except-- in so far as is necessary because some overlapping cpuset
+has "sched_load_balance" enabled.
+
+So, for example, if the top cpuset has the flag "sched_load_balance"
+enabled, then the scheduler will have one sched domain covering all
+CPUs, and the setting of the "sched_load_balance" flag in any other
+cpusets won't matter, as we're already fully load balancing.
+
+Therefore in the above two situations, the top cpuset flag
+"sched_load_balance" should be disabled, and only some of the smaller,
+child cpusets have this flag enabled.
+
+When doing this, you don't usually want to leave any unpinned tasks in
+the top cpuset that might use non-trivial amounts of CPU, as such tasks
+may be artificially constrained to some subset of CPUs, depending on
+the particulars of this flag setting in descendent cpusets.  Even if
+such a task could use spare CPU cycles in some other CPUs, the kernel
+scheduler might not consider the possibility of load balancing that
+task to that underused CPU.
+
+Of course, tasks pinned to a particular CPU can be left in a cpuset
+that disables "sched_load_balance" as those tasks aren't going anywhere
+else anyway.
+
+There is an impedance mismatch here, between cpusets and sched domains.
+Cpusets are hierarchical and nest.  Sched domains are flat; they don't
+overlap and each CPU is in at most one sched domain.
+
+It is necessary for sched domains to be flat because load balancing
+across partially overlapping sets of CPUs would risk unstable dynamics
+that would be beyond our understanding.  So if each of two partially
+overlapping cpusets enables the flag 'sched_load_balance', then we
+form a single sched domain that is a superset of both.  We won't move
+a task to a CPU outside it cpuset, but the scheduler load balancing
+code might waste some compute cycles considering that possibility.
+
+This mismatch is why there is not a simple one-to-one relation
+between which cpusets have the flag "sched_load_balance" enabled,
+and the sched domain configuration.  If a cpuset enables the flag, it
+will get balancing across all its CPUs, but if it disables the flag,
+it will only be assured of no load balancing if no other overlapping
+cpuset enables the flag.
+
+If two cpusets have partially overlapping 'cpus' allowed, and only
+one of them has this flag enabled, then the other may find its
+tasks only partially load balanced, just on the overlapping CPUs.
+This is just the general case of the top_cpuset example given a few
+paragraphs above.  In the general case, as in the top cpuset case,
+don't leave tasks that might use non-trivial amounts of CPU in
+such partially load balanced cpusets, as they may be artificially
+constrained to some subset of the CPUs allowed to them, for lack of
+load balancing to the other CPUs.
+
+1.7.1 sched_load_balance implementation details.
+------------------------------------------------
+
+The per-cpuset flag 'sched_load_balance' defaults to enabled (contrary
+to most cpuset flags.)  When enabled for a cpuset, the kernel will
+ensure that it can load balance across all the CPUs in that cpuset
+(makes sure that all the CPUs in the cpus_allowed of that cpuset are
+in the same sched domain.)
+
+If two overlapping cpusets both have 'sched_load_balance' enabled,
+then they will be (must be) both in the same sched domain.
+
+If, as is the default, the top cpuset has 'sched_load_balance' enabled,
+then by the above that means there is a single sched domain covering
+the whole system, regardless of any other cpuset settings.
+
+The kernel commits to user space that it will avoid load balancing
+where it can.  It will pick as fine a granularity partition of sched
+domains as it can while still providing load balancing for any set
+of CPUs allowed to a cpuset having 'sched_load_balance' enabled.
+
+The internal kernel cpuset to scheduler interface passes from the
+cpuset code to the scheduler code a partition of the load balanced
+CPUs in the system. This partition is a set of subsets (represented
+as an array of cpumask_t) of CPUs, pairwise disjoint, that cover all
+the CPUs that must be load balanced.
+
+Whenever the 'sched_load_balance' flag changes, or CPUs come or go
+from a cpuset with this flag enabled, or a cpuset with this flag
+enabled is removed, the cpuset code builds a new such partition and
+passes it to the scheduler sched domain setup code, to have the sched
+domains rebuilt as necessary.
+
+This partition exactly defines what sched domains the scheduler should
+setup - one sched domain for each element (cpumask_t) in the partition.
+
+The scheduler remembers the currently active sched domain partitions.
+When the scheduler routine partition_sched_domains() is invoked from
+the cpuset code to update these sched domains, it compares the new
+partition requested with the current, and updates its sched domains,
+removing the old and adding the new, for each change.
 
-1.7 How do I use cpusets ?
+1.8 How do I use cpusets ?
 --------------------------
 
 In order to minimize the impact of cpusets on critical kernel

@@ -713,6 +713,8 @@ struct sched_domain {
 #endif
 };
 
+extern void partition_sched_domains(int ndoms_new, cpumask_t *doms_new);
+
 #endif	/* CONFIG_SMP */
 
 /*

                          I won't rest till it's the best ...
                          Programmer, Linux Scalability
                          Paul Jackson <[email protected]> 1.650.933.1373

From: Paul Jackson <[email protected]>

The kernel/cpuset.c code handling the updating of a cpusets 'cpus' and 'mems' masks was starting to look a little bit crufty to me.

So I rewrote it a little bit. Other than subtle improvements in the consistency of identifying white space at the beginning and end of passed in masks, I don't see that it makes any visible difference in behaviour. But it's one or two hundred kernel text bytes smaller, and to my eye, easier to understand.

---

Andrew - this patch goes after:
cpuset-and-sched-domains-sched_load_balance-flag

 kernel/cpuset.c |   50 ++++++++++++++++++++------------------------------
 1 file changed, 20 insertions(+), 30 deletions(-)

@@ -488,6 +488,14 @@ static int validate_change(const struct 
 			return -EINVAL;
 	}
 
+	/* Cpusets with tasks can't have empty cpus_allowed or mems_allowed */
+	if (cgroup_task_count(cur->css.cgroup)) {
+		if (cpus_empty(trial->cpus_allowed) ||
+	    	    nodes_empty(trial->mems_allowed)) {
+			return -ENOSPC;
+		}
+	}
+
 	return 0;
 }
 

@@ -691,11 +699,13 @@ static int update_cpumask(struct cpuset 
 	trialcs = *cs;
 
 	/*
-	 * We allow a cpuset's cpus_allowed to be empty; if it has attached
-	 * tasks, we'll catch it later when we validate the change and return
-	 * -ENOSPC.
+	 * An empty cpus_allowed is ok iff there are no tasks in the cpuset.
+	 * Since cpulist_parse() fails on an empty mask, we special case
+	 * that parsing.  The validate_change() call ensures that cpusets
+	 * with tasks have cpus.
 	 */
-	if (!buf[0] || (buf[0] == '\n' && !buf[1])) {
+	buf = strstrip(buf);
+	if (!*buf) {
 		cpus_clear(trialcs.cpus_allowed);
 	} else {
 		retval = cpulist_parse(buf, trialcs.cpus_allowed);

@@ -703,10 +713,6 @@ static int update_cpumask(struct cpuset 
 			return retval;
 	}
 	cpus_and(trialcs.cpus_allowed, trialcs.cpus_allowed, cpu_online_map);
-	/* cpus_allowed cannot be empty for a cpuset with attached tasks. */
-	if (cgroup_task_count(cs->css.cgroup) &&
-	    cpus_empty(trialcs.cpus_allowed))
-		return -ENOSPC;
 	retval = validate_change(cs, &trialcs);
 	if (retval < 0)
 		return retval;

@@ -811,29 +817,19 @@ static int update_nodemask(struct cpuset
 	trialcs = *cs;
 
 	/*
-	 * We allow a cpuset's mems_allowed to be empty; if it has attached
-	 * tasks, we'll catch it later when we validate the change and return
-	 * -ENOSPC.
+	 * An empty mems_allowed is ok iff there are no tasks in the cpuset.
+	 * Since nodelist_parse() fails on an empty mask, we special case
+	 * that parsing.  The validate_change() call ensures that cpusets
+	 * with tasks have memory.
 	 */
-	if (!buf[0] || (buf[0] == '\n' && !buf[1])) {
+	buf = strstrip(buf);
+	if (!*buf) {
 		nodes_clear(trialcs.mems_allowed);
 	} else {
 		retval = nodelist_parse(buf, trialcs.mems_allowed);
 		if (retval < 0)
 			goto done;
-		if (!nodes_intersects(trialcs.mems_allowed,
-						node_states[N_HIGH_MEMORY])) {
-			/*
-			 * error if only memoryless nodes specified.
-			 */
-			retval = -ENOSPC;
-			goto done;
-		}
 	}
-	/*
-	 * Exclude memoryless nodes.  We know that trialcs.mems_allowed
-	 * contains at least one node with memory.
-	 */
 	nodes_and(trialcs.mems_allowed, trialcs.mems_allowed,
 						node_states[N_HIGH_MEMORY]);
 	oldmem = cs->mems_allowed;

@@ -841,12 +837,6 @@ static int update_nodemask(struct cpuset
 		retval = 0;		/* Too easy - nothing to do */
 		goto done;
 	}
-	/* mems_allowed cannot be empty for a cpuset with attached tasks. */
-	if (cgroup_task_count(cs->css.cgroup) &&
-	    nodes_empty(trialcs.mems_allowed)) {
-		retval = -ENOSPC;
-		goto done;
-	}
 	retval = validate_change(cs, &trialcs);
 	if (retval < 0)
 		goto done;

                          I won't rest till it's the best ...
                          Programmer, Linux Scalability
                          Paul Jackson <[email protected]> 1.650.933.1373

I don't like adding these funny special case sort of things like this. The user should just be able to specify exactly the partitioning of tasks required, and cpusets should ask the scheduler to do the best job of load balancing possible.

I implemented that with my patches to do automatic discovery of the largest set of disjoint cpusets.

way to specify that the machine should be partitioned (IIRC because stuff defaults to going into the root cpuset which covers all CPUs?).

Instead of adding these "I want the scheduler to do something a bit vague but hopefully good albeit with some downsides" flags, there should be a way to say "I want to partition the CPUs like so...", IMO.

Barring that (ie. maybe you always want a root cpuset to cover all CPUs), then maybe we should retain the spanning sched domains in order to balance the root cpuset, and add another set of domains according to cpuset partitioning. This could be entirely transparent to userspace, I think (using my patch).

Just my opinion. Good to see more thought going into this area, because it is something that sched-domains can do really well but is underused.

If the cpusets which have 'sched_load_balance' enabled are disjoint (their 'cpus' cpus_allowed masks don't overlap) then you get exactly what you're asking for. In that case there is exactly one sched domain for the 'cpus' allowed by each cpuset that has sched_load_balanced enabled.

But there is another case in which one does not want what you ask for.

That case involves the situation where one is running a third part batch scheduler on part of ones big system, and doing other stuff (perhaps Ingo's realtime stuff) on another part of the system.

In that case, the system admin will be advised to turn off sched_load_balance on the top cpuset. But in that case the system admin will -not- know from moment to moment what jobs the batch scheduler is running on the cpus assigned to its control. Only the batch scheduler knows that.

The batch scheduler is code that was written by someone else, in some other company, some other time. That code does not get to control the overall sched domain partitioning of the entire system. The batch scheduler gets to say, in affect:

Here's where I need load balancing to occur, in the normal fashion, and here's where I don't need it.

In short, you insisting that only a single administrative point of control determine the systems sched domains. Sometimes that fits the way the system is managed, and my patch lets you do that. But sometimes this is a shared responsibility, between a piece of third party software and the system admin, and my patch allows for that case as well.

This is a typical sort of situation that arises from having hierarchical cpuset definitions, and highlights the reason (and the use case, involving third party batch schedulers) that I went with a hierarchical cpuset architecture in the first place.

                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <[email protected]> 1.925.600.0401

But you could do that just by having the current cpuset scheme able to properly partition the system. You can't (easily) do this now because you have so many tasks in the root cpuset that it is impossible to know whether or not you actually want to load balance them.

You would do this by creating partitioning cpusets which carve up the root cpuset (basically -- have multiple roots).

In this case the admin would simply not partition the system (they would retain a single root cpuset).

Neither approach is really fundamentally more or less powerful than the other, but what I object to in yours is adding these flags which don't allow the admin to specify what they want, but to specify how they want it done.

Moreover, sched_load_balance doesn't really sound like a good name for asking for a partition. It's more like you're just asking to have better load balancing over that set, which you could equally achieve by adding a second set of sched domains (and the global domains could keep globally balancing).

Basically: the admin doesn't know best when it comes to how the scheduler should work; the admin knows best about how they intend the system to be used.

Rather than require the admin to know the intricate details about how and why the scheduler load balancing gets broken, and when they might or might not need to use this flag, they can just specify what they want to be done, and the kernel can choose the optimal strategy.

No, I'm insisting that *no* single administrative point of control determines the sched domains. Not directly. The kernel should. cpusets API should be rich enough that the kernel can derive tihs information from what the admin has intended.

Yup - it's not a good name for asking for a partition.

That's because it isn't asking for a partition.

It's asking for load balancing over the CPUs in the cpuset so marked.

Yup - it's asking for load balancing over that set. That is why it is called that. There's no idea here of better or worse load balancing, that's an internal kernel scheduler subtlety -- it's just a request that load balancing be done.

That is what is visible to user space: whether or not tasks get moved from overloaded CPUs to underloaded, though still allowed, CPUs.

This is visible to user space in two ways:
1) as task movemement, which may or may not be what is desired, and
2) as kernel CPU cycles spent, because load balancing costs CPU cycles that increase more than linearly with the number of CPUs being balanced.

The user doesn't give a hoot what a 'sched domain' is. They care to manage (1) whether their tasks might move under a load imbalance, and
(2) how many CPU cycles the kernel spends providing this service.

You would do this with the current, single rooted cpuset (and now cgroup) mechanism by having multiple immediate child cpusets of the root cpuset, which partition the system CPUs. There is no need to invent some bastardized multiple root structure.

I don't know what proposal you are reacting to here. Clearly not this patch that I have proposed, as it is trivially easy to indicate whether you want to load balance the root cpuset - by setting or clearing the 'sched_load_balance' flag in the root cpuset.

How could it possibly get any more direct that that?

My approach doesn't do that - perhaps we aren't communicating.

We are in complete agreement that the admin should specify what they want, and leave it to the kernel to figure out how to do it.

Excellent -- I'm glad you like my approach </sarcasm>

We are in complete agreement in insisting on this.

In short:

The kernel schedulers dynamic sched domains are --not-- the service being provided to the user. "Sched domains" are just the kernel internal mechanism.

The service being provided is dynamic load balancing of tasks from overloaded CPUs to underloaded CPUs.

Some users will want to disable load balancing on some cpusets, because either:
(1) it's too expensive to balance really large cpusets unless really needed, or
(2) real time users don't want to waste the CPU cycles doing balancing even on small cpusets.

If you think I repeated everything two or three times above ... good, you're right - I did.

                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <[email protected]> 1.925.600.0401

Yeah yeah OK, you turn it off in the parent cpuset of the child cpusets which you want the partitioning to occur in, and ensure there are no other overlapping cpusets with that flag turned on in order to create a hard partition. I don't think this makes the API anynicer.

OK, if it prohibits balancing when sched_load_balance is 0, then it is slightly more useful.

Yeah, but the interface is not very nice. As an interface for hard partitioning, it doesn't work nicely because it is hierarchical.

What do you mean by bastardized? What's wrong with having a real (and sane) representation of the requested hard-partitions in the system?

Not your proposal, just the idea to have enough information to be able to work out a more optimal set of sched-domains automatically. Actually we can do most of it already automatically, but not hard partitioning.

[snip]

As I said, neither is really semantically more powerful than the other. So yeah those things are possible to do with your API, but I don't like the API.

It doesn't prohibit load balancing just because sched_load_balance is 0. Only if there are no overlapping cpusets still needing balancing does it prohibit balancing when 0.

Yeah -- cpusets are hierarchical. And some of the use cases for which cpusets are designed are hierarchical.

Changing cpusets from single root to multiple roots would be bastardizing it.

My proposed sched_load_balance API is already quite capable of representing what you see the need for - hard partitioning. It is also quite capable of representing some other situations, such as I've described in other replies, that you don't seem to see the need for.

To repeat myself, in some cases, such as batch schedulers running in a subset of the CPUs on a large system, the code that knows some of the needs for load balancing does not have system wide control to mandate hard partitioning. The batch scheduler can state where it is depending on load balancing being present, and the system administrator can choose or not to turn off load balancing in the top cpuset, thereby granting or not control over load balancing on the CPUs controlled by the batch scheduler to the batch scheduler.

Hard partitioning is not the only use case here.

If you don't appreciate the other cases, then fine ... but I don't think that gives you grounds to reject a patch just because it is not precisely the ideal, narrowly focused, API for the case you do appreciate.

What's wrong with it is that 1) it doesn't cover all the use cases,
2) it would require a new and different mechanism other than cpusets which are not multiple rooted, and do robustly support overlapping sets and hence are not a hard partitioning, and 3) we'd still need the cpuset based API to cover the remaining use cases.

Good grief -- I must be misunderstanding you here, Nick. I can't imagine that you want to turn cpusets into a multiple rooted hard partition mechanism. If you are, then "bastardized" is the right word.

I can't figure out what the sentence is saying ... sorry.

                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <[email protected]> 1.925.600.0401

Yeah, that's what I mean. Important point: prohibits, rather than better/worse.

But partitioning isn't.

Well OK, if that's your definition. Not very helpful though.

Can I win this argument by defining sched_load_balance to crapify it? :)

Why isn't that possible with my approach?

What happens when you partition the system with your approach, and you get kernel threads being spawned into the root cpuset and getting unbalanced?

With my approach, these can get naturally balanced.

OK, you haven't explained why not.

Obviously any approach cannot retain the existing kernel API, true.

I just still don't understand how those cases work... if you can spell it out for me.

The above sentence was explaining which proposal I was talking about.

Yup. We've got a square peg and a round hole. An impedance mismatch. That's the root cause of this entire wibbling session, in my view.

The essential role of cpusets, cgroups and much other such work of recent, in my view, is pounding this square peg into that round hole. In essence, it is fitting the hierarchical structure of the organizations (corporations, universities and governments) who own big systems to the flat, system-wide mandates needed to manage a given computer system.

Well, such a change would be rather substantial and undesired, if those terms help you more.

If I understand your approach to the kernel-to-user interface correctly (sometimes I doubt I do) then your approach expected some user space code or person or semi-intelligent equivalent to define a flat partition, which will then be used to determine the sched domains.

In the batch scheduler case, running on a large shared system used perhaps by several departments, no one entity can do that. One person, perhaps the system admin, knows if they want to give complete control of some big chunk of CPUs to a batch scheduler. The batch scheduler, written by someone else far away and long ago, knows which jobs are actively running on which subsets of the CPUs the batch scheduler is using.

There is no single monolithic entity on such systems who knows all and can dictate all details of a single, flat, system-wide partitioning.

The partitioning has to be sythesized from the combined requests of several user space entities. That's ok -- this is bread and butter work for cpusets.

                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <[email protected]> 1.925.600.0401

Basically, yeah.

OK, so I don't exactly understand you either. To make it simple, can you give a concrete example of a cpuset hierarchy that wouldn't work?

OK, so to really do anything different (from a non-partitioned setup), you would need to set sched_load_balance=0 for the root cpuset? Suppose you do that to hard partition the machine, what happens to newly created tasks like kernel threads or things that aren't in a cpuset?

Yup - exactly. In fact one code fragment in my patch highlights this:

        /* Special case for the 99% of systems with one, full, sched domain */
        if (is_sched_load_balance(&top_cpuset)) {
                ndoms = 1;
                doms = kmalloc(sizeof(cpumask_t), GFP_KERNEL);
                *doms = top_cpuset.cpus_allowed;
                goto rebuild;
        }

This code says: if the top cpuset is load balanced, you've got one big fat sched domain covering all (nonisolated) CPUs - end of story. None of the other 'sched_load_balance' flags matter in this case.

Logically, the above code fragment is not needed. Without it, the code would still do the same thing, just wasting more CPU cycles doing it.

Well ... --every-- task is in a cpuset, always. Newly created tasks start in the cpuset of their parent. Grep for 'the_top_cpuset_hack' in kernel/cpuset.c to see the lengths to which we go to ensure that current->cpuset always resolves somewhere.

The usual case on the big systems that I care about the most is that we move (almost) every task out of the top cpuset, into smaller cpusets, because we don't want some random thread intruding on the CPUs dedicated to a particular job. The only threads left in the root cpuset are pinned kernel threads, such as for thread migration, per-cpu irq handlers and various per-cpu and per-node disk and file flushers and such. These threads aren't going anywhere, regardless. But no thread that is willing to run anywhere is left free to run anywhere.

I will advise my third party batch scheduler developers to turn off sched_load_balance on their main cpuset, and on any big "holding tank" cpusets they have which hold only inactive jobs. This way, on big systems that are managed to optimize for this, the kernel scheduler won't waste time load balancing the batch schedulers big cpusets that don't need it. With the 'sched_load_balance' flag defined the way it is, the batch scheduler won't have to make system-wide decisions as to sched domain partitioning. They can just make local 'advisory' markings on particular cpusets that (1) are or might be big, and (2) don't hold any active tasks that might need load balancing. The system will take it from there, providing the finest granularity sched domain partitioning that will accomplish that.

I will advise the system admins of bigger systems to turn off sched_load_balance on the top cpuset, as part of the above work routinely done to get all non-pinned tasks out of the top cpuset.

I will advise the real time developers using cpusets to: (1) turn off sched_load_balance on their real time cpusets, and (2) insist that the sys admins using their products turn off sched_load_balance on the top cpuset, to ensure the expected realtime performance is obtained.

Most systems, even medium size ones (for some definition of medium, perhaps dozens of CPUs?) so long as they aren't running realtime on some CPUs, can just run with the default - one big fat load balanced sched domain ... unless of course they have some other need not considered above.

                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <[email protected]> 1.925.600.0401

OK, then non-balancing cpuset.

These are what I'm worried about, and things like kswapd, pdflush, could definitely use a huge amount of CPU.

If you are interested in hard partitioning the system, you most definitely want these things to be balanced across the non-isolated CPUs.

But these guys are pinned anyway (or else they would already be moved into a smaller load balanced cpuset), so why waste time load balancing what can't move?

And on some of the systems I care about, we don't want to load balance these guys; rather we go to great lengths to see that they don't run at all when we don't want them to.

                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <[email protected]> 1.925.600.0401

They're not pinned (kswapds are pinned to a node, but still). pdflush is not pinned at all and can be dynamically created and destroyed. Ditto for kjournald, as well as many others.

Basically: it doesn't feel like a satisfactory solution to brush these under the carpet.

Most smaller realtime partitioned systems will want to, I'd expect.

Whatever is not pinned is moved out of the top cpuset, on the kind of systems I'm most familiar with. They are put in a smaller cpuset, with load balancing, that is sized for the workload they might present, but kept separate from the main jobs.

We don't do a whole lot of brushing under the carpet on these kind of systems. If I gave you the impression we do, then I misled you - sorry.

                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <[email protected]> 1.925.600.0401

So if a new pdflush is spawned, it get's moved to some cpuset? That probably isn't something these realtime systems want to do (ie. the non-realtime portion probably doesn't want to have any sort of scheduler or even worry about cpusets at all).

No, not on your systems. I'm worried about the smaller ones that don't get so much attention (eg. hard partitioning for realtime).

No - the new pdflush is put in the same cpuset as its parent, with a patch that I sent in early this year. See the following code in mm/pdflush.c:

/*
* Some configs put our parent kthread in a limited cpuset,
* which kthread() overrides, forcing cpus_allowed == CPU_MASK_ALL.
* Our needs are more modest - cut back to our cpusets cpus_allowed.
* This is needed as pdflush's are dynamically created and destroyed.
* The boottime pdflush's are easily placed w/o these 2 lines. */
cpus_allowed = cpuset_cpus_allowed(current); set_cpus_allowed(current, cpus_allowed);

return __pdflush(&my_work);

                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <[email protected]> 1.925.600.0401

It's more a matter of knowing how my third party batch scheduler coders think. They will be off in some corner of their code with a cpuset in hand that they know is just being used to hold inactive (paused) tasks, and they can likely be persuaded to mark those cpusets as not being in need of any wasted CPU cycles load balancing them.

But these inactive cpusets will overlap in unknown (to them at the time, in that piece of code) ways with other cpusets holding active jobs, and there is no chance, unless it is a matter of major performance impact, that they will be in any position to comment on the proper partitioning of the sched domains on all the CPUs under the control of their batch scheduler, much less comment on the partitioning of the rest of the system.

                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <[email protected]> 1.925.600.0401

There won't be any CPU cycles used, if the tasks are paused (surely they're not spin waiting).

Consider the case when there are two, smaller, non-overlapping cpusets with active jobs, and one larger cpuset, covering both those smaller ones, with only paused tasks.

If we realize we don't need to balance the larger cpuset, then we can have two smaller sched domains rather than one larger one.

Since the CPU cycle cost of load balancing increases more than linearly with the size of the sched domain, therefore it will save CPU cycles to have the two smaller ones, rather than the one larger one.

If user space can just tell us that the larger cpuset doesn't need balancing, then the kernel has enough information to perform this optimization.

                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <[email protected]> 1.925.600.0401

Hmmm ... this could be the key to this discussion.

Nick - can two sched domains overlap? And if they do, what does that mean on any user or application behaviour.

into one sched domain. If two cpusets with overlapping 'cpus' are both marked 'sched_load_balance', then this patch forms a single, combined sched domain.

As best as I can tell, you and I are actually in agreement in the case that there is no overlap. If the several cpusets which have 'sched_load_balance' enabled have mutually disjoint 'cpus' (no overlap), then my patch forms exactly one sched domain for each such cpuset, having the same 'cpus'.

The issue is the overlapping cases - are overlapping sched domains allowed, and if so, how do they affect user space?

                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <[email protected]> 1.925.600.0401

Yes, sched domains can be completely arbitrary, and of course in the current kernel, parent domains always overlap their children.

A sched domain usually means that the scheduler can move tasks around among that group of CPUs, given the correct flags (but if there are no flags, then it would be a superfluous domain and should get trimmed away I think).

BTW. as far as the sched.c changes in your patch go, I much prefer the partition_sched_domains API: http://lkml.org/lkml/2006/10/19/85

The caller should manage everything itself, rather than partition_sched_domains doing half of the memory allocation.

OK, I don't think your patch actually does the wrong thing technically (although admittedly your rebuild_sched_domains isn't something I really applied my poor brain to).

For hard partitions, you don't want them of course. And I think we should come up with a cpusets solution for that first.

Afterwards, overlapping sched domains are allowed and could be used to make balancing more efficient (rather than any real affect on userspace). At the moment, the domain builder probably wouldn't cope very well, though.

i've merged your patch to my scheduler queue - see the patch below. (And could you send me your SoB line too?) Paul, if we went with the patch below, what else would be needed for your purposes?

Ingo

--------------------------------->
Subject: sched: fix sched-domains partitioning by cpusets
From: Nick Piggin <[email protected]>

Fix sched-domains partitioning by cpusets. Walk the whole cpusets tree after something interesting changes, and recreate all partitions.

---
 include/linux/cpuset.h |    2 
 include/linux/sched.h  |    3 -
 kernel/cpuset.c        |  109 ++++++++++++++++++++++---------------------------
 kernel/sched.c         |   31 +++++++------
 4 files changed, 70 insertions(+), 75 deletions(-)

Index: linux/include/linux/cpuset.h
===================================================================
@@ -14,6 +14,8 @@
 
 #ifdef CONFIG_CPUSETS
 
+extern int cpuset_hotplug_update_sched_domains(void);
+
 extern int number_of_cpusets;	/* How many cpusets are defined in system? */
 
 extern int cpuset_init_early(void);

Index: linux/include/linux/sched.h
===================================================================
@@ -798,8 +798,7 @@ struct sched_domain {
 #endif
 };
 
-extern int partition_sched_domains(cpumask_t *partition1,
-				    cpumask_t *partition2);
+extern int partition_sched_domains(cpumask_t *partition);
 
 #endif	/* CONFIG_SMP */
 

Index: linux/kernel/sched.c
===================================================================
@@ -6274,6 +6274,9 @@ error:
  */
 static int arch_init_sched_domains(const cpumask_t *cpu_map)
 {
+#ifdef CONFIG_CPUSETS
+	return cpuset_hotplug_update_sched_domains();
+#else
 	cpumask_t cpu_default_map;
 	int err;
 

@@ -6287,6 +6290,7 @@ static int arch_init_sched_domains(const
 	err = build_sched_domains(&cpu_default_map);
 
 	return err;
+#endif
 }
 
 static void arch_destroy_sched_domains(const cpumask_t *cpu_map)

@@ -6310,29 +6314,26 @@ static void detach_destroy_domains(const
 
 /*
  * Partition sched domains as specified by the cpumasks below.
- * This attaches all cpus from the cpumasks to the NULL domain,
+ * This attaches all cpus from the partition to the NULL domain,
  * waits for a RCU quiescent period, recalculates sched
- * domain information and then attaches them back to the
- * correct sched domains
- * Call with hotplug lock held
+ * domain information and then attaches them back to their own
+ * isolated partition.
+ *
+ * Called with hotplug lock held
+ *
+ * Returns 0 on success.
  */
-int partition_sched_domains(cpumask_t *partition1, cpumask_t *partition2)
+int partition_sched_domains(cpumask_t *partition)
 {
+	cpumask_t non_isolated_cpus;
 	cpumask_t change_map;
-	int err = 0;
 
-	cpus_and(*partition1, *partition1, cpu_online_map);
-	cpus_and(*partition2, *partition2, cpu_online_map);
-	cpus_or(change_map, *partition1, *partition2);
+	cpus_andnot(non_isolated_cpus, cpu_online_map, cpu_isolated_map);
+	cpus_and(change_map, *partition, non_isolated_cpus);
 
 	/* Detach sched domains from all of the affected cpus */
 	detach_destroy_domains(&change_map);
-	if (!cpus_empty(*partition1))
-		err = build_sched_domains(partition1);
-	if (!err && !cpus_empty(*partition2))
-		err = build_sched_domains(partition2);
-
-	return err;
+	return build_sched_domains(&change_map);
 }
 
 #if defined(CONFIG_SCHED_MC) || defined(CONFIG_SCHED_SMT)

Nick and I already resolved that, when he first posted this patch in October of 2006. The cpu_exclusive flag doesn't work for this.

Here's a copy of the key message, from Nick, near the end of that thread in which he earlier proposed this patch, also available at:
http://lkml.org/lkml/2006/10/21/12

====================================================
Paul Jackson wrote:
> Nick wrote:
>
>>Or, another question, how does my patch hijack cpus_allowed? In >>what way does it change the semantics of cpus_allowed? >
>
> It limits load balancing for tasks in cpusets containing > a superset of that cpusets cpus.
>
> There are always such cpusets - the top cpuset if no other.

Ah OK, and there is my misunderstanding with cpusets. From the documentation it appears as though cpu_exclusive cpusets are made in order to do the partitioning thing.

If you always have other domains overlapping them (regardless that it is a parent), then what actual use does cpu_exclusive flag have?
====================================================

I agree with Nick on this conclusion, and with his other conclusion that the 'cpu_exclusive' flag is pretty near useless.

Some per-cpuset flag other the 'cpu_exclusive' is required to control sched domains from cpusets.

This has specific impact on one of the key users of cpusets, the various developers of batch schedulers. One by one, they have determined that the cpu_exclusive flag is incompatible with the way they set up cpusets, and have decided they should not enable that flag on any cpuset under their control. It gets in their way, and serves no useful purpose for them. However we need someway for them to specify where they need load balancing, so that on large systems, they can allow the admin to avoid the cost of load balancing over the batch schedulers entire subset of the system at once, but rather just load balance over the smaller sets where the batch scheduler has active jobs running that might depend on load balancing.

Batch schedulers need to be able to specify where they need load balancing and where they don't, and they can't use the 'cpu_exclusive' flag. The defining characteristic of 'cpu_exclusive' is no overlap of CPUs with sibling cpusets. That is incompatible with their needs.

Therefore, they need a different flag.

I must NAQ this patch, and I'm surprised to see Nick propose it again, as I thought he had already agreed that it didn't suffice.

                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <[email protected]> 1.925.600.0401

ok. Then lets go back to the original plan: your two patches and the new flag. Nick?

Ingo

Sorry for the confusion: I only meant the sched.c part of that patch, not the full thing.

Ah - ok. We're getting closer then. Good.

Let me be sure I've got this right then.

You prefer the interface from your proposed patch, by which the cpuset code passes sched domain requests to the scheduler code a single cpumask that will define a sched domain:

int partition_sched_domains(cpumask_t *partition)

and I am suggesting instead a new and different interface:

void partition_sched_domains(int ndoms_new, cpumask_t *doms_new)

In the first API, one cpumask is passed in, and a single sched domain is formed, taking those CPUs from any sched domain they might have already been a member of, into this new sched domain.

In the second API, the entire flat partitioning is passed in, giving an array of masks, one mask for each desired sched domain. The passed in masks do not overlap, but might not cover all CPUs.

Question -- how does one turn off load balancing on some CPUs using the first API?

Does one do this by forming singleton sched domains of one CPU each? Is there any downside to doing this?

The simplest cpuset code to work with this would end up exposing this method of disabling load balancing to user space, forcing users to create cpusets with one CPU each to be able do disable load balancing.

However a little bit of additional kernel cpuset code could hide this detail from user space, by recognizing when the user had asked to turn off load balancing on some larger cpuset, and by then calling partition_sched_domains() multiple times, once for each CPU in that cpuset.

There might be an even simpler way. If the kernel/sched.c routines detach_destroy_domains() and build_sched_domains() were exposed as external routines, then the cpuset code could call them directly, removing the partition_sched_domains() routine from sched.c entirely. Would this be worth persuing?

                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <[email protected]> 1.925.600.0401

in any case i'd like to see the externally visible API get in foremost - and there now seems to be agreement about that. (yay!) Any internal shaping of APIs can be done flexibly between cpusets and the scheduler.

Ingo

Yup - though Nick and I will have to agree to -some- internal interface between the cpuset and sched code, at least for the moment.

At least, if we thrash about on this, we won't be changing the externally visible API around. We'll just continue driving Andrew nuts, not our users - that's an improvement.

                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <[email protected]> 1.925.600.0401

OK look, I don't want to hold up progress. I do like to ask these questions and be difficult if I think there might be a better way and/or to make sure you've thought about all the angles. I'm not volunteering to maintain cpusets and I'm not as close to the customers who care as you.

Obviously what your patches do here is a lot closer to "the right thing" than cpus_exclusive. And the worst problem they'll cause is to add cruft to cpusets.c.

So I'll keep persuing the other subthread for the same reasons, but aside from implementation nits, I don't know if it is worth holding up a merge.

Yep.

Yes, and no (it does the same thing as your version internally, so no downside).

Yeah: do all that in cpusets. It's already information you would have to derive in order to make it work properly anyway. If you are not passing in the singleton domains ATM, then they will not get properly detached and isolated.

detach_destroy and build are things that may get reimplemented to suit different capabilities (eg. we might want to have multiple trees of domains for each CPU). So I think it is important to expose the simple partition API which should be unambiguous and stable.

It's not a huge deal, but I'd like to keep partition_sched_domains. After my patch, it's really simple.

ok

ok

It's a deal.

I've got a couple of brown paper bag bug fixes almost ready to send out, for the patch I sent Andrew a few days ago:

cpuset and sched domains: sched_load_balance flag

I'll send these in, and then get some sleep and code up these changes to the partition_sched_domains, along the lines you have recommended.

Thanks, Nick and Ingo.

                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <[email protected]> 1.925.600.0401

Please take a closer look at my partition_sched_domains() and its interface to the scheduler.

You should recognize this API, once you look at it. It simply passes the full flat, hard partition, in its entirety. This is the partitioning that you speak of, I believe. It's here; just not where you expected it.

The portion of the code that is in kernel/sched.c is just a little bit of optimization. It avoids rebuilding all the sched domains and reattaching every task to its sched domain; rather it determines which sched domains were added or removed and just rebuilds them.

Once you take a closer look, I hope you will agree that this new interface between the cpuset and sched code provides a cleaner separation.

                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <[email protected]> 1.925.600.0401

I don't know what you think I said that is incorrect and requires me to look at again. I don't like your partition_sched_domains API because of the allocation thing. So I prefer the existing (or better, the simplified version in my patch referenced).

The caller should determine which domain to rebuild and reattach. Simple.

i like this, this feature would be quite useful for -rt and CPU shielding.

( a cpuset is a mandatory container for set_cpus_allowed(), so there is
a material and app-visible difference between a 4-CPU cpuset that has balancing disabled and 4x 1-CPU cpusets. )

Ingo

...

Are there some attributions missing, else S-O-B ?

...

	q = csa = doms = NULL;

	q = NULL;
	csa = NULL;
	doms = NULL;

...

Thanks for the review, Randy. Good comments.

Yup - I should have written this line as:

It makes no difference to the code generated. I tend to leave out 'compiler optimization' hint words if I don't need them to get the compiler to optimize. In this case, of a single use file static routine, the compiler inlines anyway.

You're right - and Andrew would be right as well, since the form:

	q = csa = doms = NULL;

generates a compiler warning, as not all three pointers are the same type.

So three lines of code it must be.

Yup - you're right - about the 'csa' check.

However the if(q ...) check is needed, because I have another bug here. I allocated 'q' using kfifo_alloc(), so must free using kfifo_free (or else leak the kfifo buffer memory.) Calls to kfifo_free() have to guard against NULL pointers before the call.

Thanks, Randy!

                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <[email protected]> 1.925.600.0401