sched/numa: Introduce sys_numa_{t,m}bind()

Commit-ID:  3a0fea961b98d1838f35dba51a639d40f4a5589f
Gitweb:     http://git.kernel.org/tip/3a0fea961b98d1838f35dba51a639d40f4a5589f
Author:     Peter Zijlstra <[email protected]>
AuthorDate: Thu, 8 Mar 2012 17:56:08 +0100
Committer:  Ingo Molnar <[email protected]>
CommitDate: Fri, 18 May 2012 08:16:27 +0200

sched/numa: Introduce sys_numa_{t,m}bind()

Now that we have a NUMA process scheduler, provide a syscall interface for finer granularity NUMA balancing. In particular this allows setting up NUMA groups of threads and vmas within a process.

For this we introduce two new syscalls:

sys_numa_tbind(int tig, int ng_id, unsigned long flags);

Bind a thread to a numa group, query its binding or create a new group:

sys_numa_tbind(tid, -1, 0); // create new group, return new ng_id
sys_numa_tbind(tid, -2, 0); // returns existing ng_id
sys_numa_tbind(tid, ng_id, 0); // set ng_id

Returns:
-ESRCH tid->task resolution failed
-EINVAL task didn't have a ng_id, flags was wrong
-EPERM we don't have privileges over tid

sys_numa_mbind(unsigned long addr, unsigned long len, int ng_id, unsigned long flags);

Bind a memory region to a numa group.

sys_numa_mbind(addr, len, ng_id, 0);

create a non-mergable vma over [addr,addr+len) and assign an mpol binding it to the numa group identified by ng_id.

These system calls together can create thread and vma groups which will be scheduled as a single entity.

---
 arch/x86/syscalls/syscall_32.tbl |    2 +
 arch/x86/syscalls/syscall_64.tbl |    2 +
 include/asm-generic/unistd.h     |    6 +-
 include/linux/mempolicy.h        |   27 ++
 include/linux/mm.h               |   16 +
 include/linux/sched.h            |    2 +
 include/linux/syscalls.h         |    3 +
 kernel/exit.c                    |    1 +
 kernel/sched/numa.c              |  646 ++++++++++++++++++++++++++++++++++++++
 kernel/sys_ni.c                  |    4 +
 mm/memory.c                      |    5 +-
 mm/mempolicy.c                   |    8 +-
 12 files changed, 718 insertions(+), 4 deletions(-)

index 29f9f05..38954c5 100644
@@ -355,3 +355,5 @@
 346	i386	setns			sys_setns
 347	i386	process_vm_readv	sys_process_vm_readv		compat_sys_process_vm_readv
 348	i386	process_vm_writev	sys_process_vm_writev		compat_sys_process_vm_writev
+349	i386	numa_mbind		sys_numa_mbind			compat_sys_numa_mbind
+350	i386	numa_tbind		sys_numa_tbind			compat_sys_numa_tbind

index dd29a9e..63c5285 100644
@@ -318,6 +318,8 @@
 309	common	getcpu			sys_getcpu
 310	64	process_vm_readv	sys_process_vm_readv
 311	64	process_vm_writev	sys_process_vm_writev
+312	64	numa_mbind		sys_numa_mbind
+313	64	numa_tbind		sys_numa_tbind
 #
 # x32-specific system call numbers start at 512 to avoid cache impact
 # for native 64-bit operation.

index 991ef01..4dfef49 100644
@@ -691,9 +691,13 @@ __SC_COMP(__NR_process_vm_readv, sys_process_vm_readv, \
 #define __NR_process_vm_writev 271
 __SC_COMP(__NR_process_vm_writev, sys_process_vm_writev, \
           compat_sys_process_vm_writev)
+#define __NR_numa_mbind 272
+__SC_COMP(__NR_numa_mbind, sys_numa_mbind, compat_sys_ms_mbind)
+#define __NR_numa_tbind 273
+__SC_COMP(__NR_numa_tbind, sys_numa_tbind, compat_sys_ms_tbind)
 
 #undef __NR_syscalls
-#define __NR_syscalls 272
+#define __NR_syscalls 274
 
 /*
  * All syscalls below here should go away really,

index af2983b..6e1029f 100644
@@ -79,6 +79,8 @@ enum mpol_rebind_step {
 #include <linux/nodemask.h>
 #include <linux/pagemap.h>
 #include <linux/migrate.h>
+#include <linux/list.h>
+#include <linux/sched.h>
 
 struct mm_struct;
 

@@ -110,6 +112,10 @@ struct mempolicy {
 	atomic_t refcnt;
 	unsigned short mode; 	/* See MPOL_* above */
 	unsigned short flags;	/* See set_mempolicy() MPOL_F_* above */
+	struct numa_group *numa_group;
+	struct list_head ng_entry;
+	struct vm_area_struct *vma;
+	struct rcu_head rcu;
 	union {
 		short 		 preferred_node; /* preferred */
 		nodemask_t	 nodes;		/* interleave/bind */

@@ -397,6 +403,27 @@ static inline int mpol_to_str(char *buffer, int maxlen, struct mempolicy *pol,
 }
 
 #endif /* CONFIG_NUMA */
+
+#ifdef CONFIG_NUMA
+
+extern void __numa_task_exit(struct task_struct *);
+extern void numa_vma_link(struct vm_area_struct *, struct vm_area_struct *);
+extern void numa_vma_unlink(struct vm_area_struct *);
+
+static inline void numa_task_exit(struct task_struct *p)
+{
+	if (p->numa_group)
+		__numa_task_exit(p);
+}
+
+#else /* CONFIG_NUMA */
+
+static inline void numa_task_exit(struct task_struct *p) { }
+static inline void numa_vma_link(struct vm_area_struct *new, struct vm_area_struct *old) { }
+static inline void numa_vma_unlink(struct vm_area_struct *vma) { }
+
+#endif /* CONFIG_NUMA */
+
 #endif /* __KERNEL__ */
 
 #endif

index a89817e..eda8271 100644
@@ -1076,19 +1076,35 @@ static inline unsigned long get_mm_counter(struct mm_struct *mm, int member)
 	return (unsigned long)val;
 }
 
+#ifdef CONFIG_NUMA
+extern void __numa_add_rss_counter(struct vm_area_struct *, int, long);
+
+static inline
+void numa_add_rss_counter(struct vm_area_struct *vma, int member, long value)
+{
+	if (vma->vm_policy) /* XXX sodding include dependecies */
+		__numa_add_rss_counter(vma, member, value);
+}
+#else /* !CONFIG_NUMA */
+static inline void numa_add_rss_counter(struct vm_area_struct *vma, int member, long value) { }
+#endif /* CONFIG_NUMA */
+
 static inline void add_rss_counter(struct vm_area_struct *vma, int member, long value)
 {
 	atomic_long_add(value, &vma->vm_mm->rss_stat.count[member]);
+	numa_add_rss_counter(vma, member, value);
 }
 
 static inline void inc_rss_counter(struct vm_area_struct *vma, int member)
 {
 	atomic_long_inc(&vma->vm_mm->rss_stat.count[member]);
+	numa_add_rss_counter(vma, member, 1);
 }
 
 static inline void dec_rss_counter(struct vm_area_struct *vma, int member)
 {
 	atomic_long_dec(&vma->vm_mm->rss_stat.count[member]);
+	numa_add_rss_counter(vma, member, -1);
 }
 
 static inline unsigned long get_mm_rss(struct mm_struct *mm)

index fe6e535..024a5f9 100644
@@ -1512,6 +1512,8 @@ struct task_struct {
 	short il_next;
 	short pref_node_fork;
 	int node;
+	struct numa_group *numa_group;
+	struct list_head ng_entry;
 #endif
 	struct rcu_head rcu;
 

index 3de3acb..9c6f47a 100644
@@ -857,5 +857,8 @@ asmlinkage long sys_process_vm_writev(pid_t pid,
 				      const struct iovec __user *rvec,
 				      unsigned long riovcnt,
 				      unsigned long flags);
+asmlinkage long sys_numa_mbind(unsigned long addr, unsigned long len,
+			       int ng_id, unsigned long flags);
+asmlinkage long sys_numa_tbind(int tid, int ng_id, unsigned long flags);
 
 #endif

index d8bd3b42..a0c1b54 100644
@@ -1018,6 +1018,7 @@ void do_exit(long code)
 	mpol_put(tsk->mempolicy);
 	tsk->mempolicy = NULL;
 	task_unlock(tsk);
+	numa_task_exit(tsk);
 #endif
 #ifdef CONFIG_FUTEX
 	if (unlikely(current->pi_state_cache))

index 47bfa16..3f5a59f 100644
@@ -103,6 +103,10 @@ cond_syscall(sys_set_mempolicy);
 cond_syscall(compat_sys_mbind);
 cond_syscall(compat_sys_get_mempolicy);
 cond_syscall(compat_sys_set_mempolicy);
+cond_syscall(sys_numa_mbind);
+cond_syscall(compat_sys_numa_mbind);
+cond_syscall(sys_numa_tbind);
+cond_syscall(compat_sys_numa_tbind);
 cond_syscall(sys_add_key);
 cond_syscall(sys_request_key);
 cond_syscall(sys_keyctl);

index 6b39551c..4614be0 100644
@@ -144,9 +144,10 @@ static void add_rss_counter_fast(struct vm_area_struct *vma, int member, int val
 {
 	struct task_struct *task = current;
 
-	if (likely(task->mm == vma->vm_mm))
+	if (likely(task->mm == vma->vm_mm)) {
 		task->rss_stat.count[member] += val;
-	else
+		numa_add_rss_counter(vma, member, val);
+	} else
 		add_rss_counter(vma, member, val);
 }
 #define inc_rss_counter_fast(vma, member) add_rss_counter_fast(vma, member, 1)

index df29149..6cdfdba 100644
@@ -291,12 +291,13 @@ struct mempolicy *mpol_new(unsigned short mode, unsigned short flags,
 		mode = MPOL_PREFERRED;
 	} else if (nodes_empty(*nodes))
 		return ERR_PTR(-EINVAL);
-	policy = kmem_cache_alloc(policy_cache, GFP_KERNEL);
+	policy = kmem_cache_alloc(policy_cache, GFP_KERNEL | __GFP_ZERO);
 	if (!policy)
 		return ERR_PTR(-ENOMEM);
 	atomic_set(&policy->refcnt, 1);
 	policy->mode = mode;
 	policy->flags = flags;
+	INIT_LIST_HEAD(&policy->ng_entry);
 
 	return policy;
 }

@@ -611,6 +612,9 @@ static int policy_vma(struct vm_area_struct *vma, struct mempolicy *new)
 	if (!err) {
 		mpol_get(new);
 		vma->vm_policy = new;
+		numa_vma_link(vma, NULL);
+		if (old)
+			numa_vma_unlink(old->vma);
 		mpol_put(old);
 	}
 	return err;

@@ -2063,11 +2067,13 @@ int vma_dup_policy(struct vm_area_struct *new, struct vm_area_struct *old)
 	if (IS_ERR(mpol))
 		return PTR_ERR(mpol);
 	vma_set_policy(new, mpol);
+	numa_vma_link(new, old);
 	return 0;
 }
 
 void vma_put_policy(struct vm_area_struct *vma)
 {
+	numa_vma_unlink(vma);
 	mpol_put(vma_policy(vma));
 }
 

I am not convinced this is the right way forward.

While this may work well for programs written in languages with pointers, and for virtual machines, I do not see how eg. a JVM could provide useful hints to the kernel, because the Java program running on top has no idea about the memory addresses of its objects, and the Java language has no way to hint which thread will be the predominant user of an object.

I like your code for handling smaller processes in NUMA systems, but we do need to have a serious discussion on how to handle processes that do not fit in one node.

The more I think about it, the more Andrea's code looks like it might be the more flexible way forward.

Another topic to discuss is whether we want lazy migrate-on-fault, or if we want to keep the program spend its time running, using another (idle) core to do the migration in the background.

All rights reversed

The home node seems to be associated with a thread and not a process. So we would be able to have multiple home nodes per process.

The whole NUMA policy thing is already quite complex and this will increase that complexity somewhat. Wish we could simplify things somehow.

Its set the same for every thread in a process, unless you use the new system calls to carve it up in pieces.

Most of that is due to existing interfaces, I'm afraid we cannot simplify without reducing those :/

I think some change to those would also be appropriate. Those have grown over a long time and there are some areas of problematic integration with the scheduler, numa policies and cpusets etc.

You're free to explore that avenue.. But afaict all these interfaces are in active use.

And yes, some of it is rather awkward, but such is the price we pay for backwards compatibility.

Well, you don't have to use it.. but you can.

This is one of the many reasons why you'll never see me use Java or any other 'managed' language.

I still have serious concerns about his approach; it very much assumes there's a temporal page<->thread relation to exploit. This might not at all be true for some programs (including JVM) that have hardly any data separation and just point chase their way around the entire object set.

Consider a database where each thread is basically scanning the global data-set at random.

Furthermore, virtual machines actively counter this assumption, a guest scheduler will move tasks between vcpus at will -- for the host this effective scrambles any page<->thread (vcpu) relation that might have existed.

I've also yet to see a coherent patch-set from Andrea with coherent changelogs and comments (this very much precludes PDFs of any kind).

And you know I detest the way he cobbled his way around the scheduler instead of integrating it properly. And I'll very much not accept anything like the spaghetti code anywhere near the scheduler I have to maintain. (I recently looked at the THP code and if that's the standard I'm not having it).

That said, I'll leave the door open and will consider something like his scanning stuff as an optional add on on-top of this.

I very much believe in doing the simple thing first, and this is that, this is much like what the userspace daemons try to do and many of the traditional Unixes have also done (albeit many of those didn't go the way of home-node migration).

I've also said many times over that I absolutely detest all the async stuff because it messes up accounting. And until someone comes up with a sane means of sorting that I'll stick to migrate-on-fault.

You also assume there's idle time elsewhere. This isn't true in general.

The other nice advantage of migrate-on-fault is that you don't have to play lifetime games with vmas. This much simplifies that aspect.

Again, simple things first.

The problem with migrate on fault in the past has been that there was no consistent benefit from the overhead added to the system. Useless page migration is a bit expensive.

I'm not sure I follow.. having the page local is a win, presuming you can limit the migration rate to something low in relation to the cost of remote accesses.

How does it matter how you migrate?

Having the page local is a win if there are a sufficient number of accesses to amortize the effort to move the page. Given the expensive nature of page migration there would need to be a large number of accesses to a page to justify the effort.

Migrate on fault incurs two types of costs:

1. Unmapping. This results in additional faults to reestablish the ptes.

2. Actual lazy migrate. More faults. Now the page needs to be copied to the new node and the actual migration work is done.

Right, but this is true of any migration scheme and not specific to MoF.

Nah, only the 1 fault is extra. Regular migration already needs to unmap and copy and reinstate, so the only extra work is the fault to trigger it.

Yes and the concern about auto migration schemes not improving performance in general applies to all migration schemes.

You are hardly a typical user, though :)

Whether we like it or not, managed runtimes are here, and people are using them in droves.

I believe that the kernel should be able to handle NUMA placement for such uses.

Neither his approach or your approach will be able to help these workloads. I do not see how that should be counted against Andrea's approach, though, since it does seem to be useful for sane workloads.

No argument there. Your scheduler integration is nicer, and Andrea's code could stand some documentation.

Leave out your syscalls (which might not be useful for managed runtimes), and you actually have the simple thing :)

I am all in favor of simplicity, and doing one thing at a time.

All rights reversed

Possibly, but it would also help if runtimes grew the capability to express such relations. That said.. I never said we shouldn't/couldn't help them eventually.

Well, if you have a sane workload you often already have strong data separation in your application, so telling the kernel about it isn't too much bother, right?

The thing is, I've been traumatized by too much exposure to the auto-parallelization crazies. I've never seen auto parallelization worth using, despite lots of presumably smart people wanting to make it happen.

Right, but the virt people could actually trivially use those, and vnuma doesn't have the scambling issue outlined earlier since the guest kernel would also try to keep home-node affinity.

Avi already said patching kvm would be like 5 minutes work.

It also absolutely avoids the false sharing issue otherwise present with per-cpu memory, since you explicitly tell it where it belongs.

These APIs also match what user-space numa daemons started doing already.

The grouping is also a natural extension to task and memory affinities and groups in general.

It also allows us to turn auto-migration off by default, which is a plus in my book. Without enough numbers I'm not convinced that we really *want* auto-discovery turned on all the time, for all workloads. The thing is, in practice most workloads that matter are short-run and even trivial forms of CPU migration doesnt ever happen for bursts of activity. We place them and that's it.

Managed runtimes on the other hand can be expected to know about and manage their locality - they do it anyway, by running guest scheduler(s). So this patch-set gives them the ability to express locality in a simple way, without the host kernel scanning actively.

We can auto-scan on top of this, if the numbers support it, but in the simple case where both the guest and the host is smart then simply expressing locality and telling each other is vastly superior to any scanning method.

Thanks,

Ingo

* Peter Zijlstra <[email protected]> wrote:

< [...]

Probably because those Unices didnt survive long enough to reach NUMA machines in earnest. SMP was a big deal already.

Thanks,

Ingo

True.

OTOH, while autonuma seems to be better for the JVM, numa sched is a significant improvement over current code:

http://lkml.indiana.edu/hypermail/linux/kernel/1204.0/01200.html

Why is that?

This depends on 931ea9d1a6e0 ("rcu: Implement per-domain single-threaded call_srcu() state machine") from core/rcu.

Indeed ...

I'll rebase it to a (by that time probably upstream) srcu commit after the merge window, once we have more fixes, have incorporated suggestions, etc. - but it's still essentially an RFC topic: [*]

Fundamentally, do people agree with the 'single home node' approach to begin with? We could turn it into a node mask, but that complicates things.

For example if there's a hierarchy of nodes, low latency and high latency ones, then it might be valid to limit to a high level (high latency) node and not specify the lower level node - while the kernel would still know about the lower level nodes as well.

Managing locality in a non-trivial cache hierarchy is hard :-/

Thanks,

Ingo

[*] I should probably move this to the tip:RFC/sched/numa
branch, to make it clear what the status of the branch is, from the commit notification emails.

I merged core/rcu locally to get a kernel that builds but ran into a divide by zero:

[    0.602181] divide error: 0000 [#1] SMP 
[    0.606159] CPU 0 
[    0.608003] Modules linked in:
[    0.611266] 
[    0.612767] Pid: 1, comm: swapper/0 Not tainted 3.4.0 #1
[    0.620912] RIP: 0010:[<ffffffff810af9ab>]  [<ffffffff810af9ab>] update_sd_lb_stats+0x38b/0x740
[    0.629630] RSP: 0018:ffff880275471870  EFLAGS: 00010056
[    0.634927] RAX: 0000000000000000 RBX: 0000000000000000 RCX: 0000000000000000
[    0.642042] RDX: 0000000000000000 RSI: ffff880475969ca0 RDI: 0000000000000000
[    0.649181] RBP: ffff880275471970 R08: ffff88027545ff60 R09: 0000000000000000
[    0.656294] R10: 0000000000000000 R11: 0000000000000001 R12: 0000000000000020
[    0.663419] R13: 0000000000000000 R14: 0000000000000000 R15: 0000000000000000
[    0.670559] FS:  0000000000000000(0000) GS:ffff88027fc00000(0000) knlGS:0000000000000000
[    0.678633] CS:  0010 DS: 0000 ES: 0000 CR0: 000000008005003b
[    0.684364] CR2: 0000000000000000 CR3: 000000000180b000 CR4: 00000000000007f0
[    0.691499] DR0: 0000000000000000 DR1: 0000000000000000 DR2: 0000000000000000
[    0.698628] DR3: 0000000000000000 DR6: 00000000ffff0ff0 DR7: 0000000000000400
[    0.705755] Process swapper/0 (pid: 1, threadinfo ffff880275470000, task ffff88027545b800)
[    0.714001] Stack:
[    0.716021]  000000000000000b 0000000000012000 0000000000000000 ffff88087fd92000
[    0.723455]  ffff880275471b5c 00000000754718b8 fffffffffffffff8 ffff880275471ab0
[    0.730884]  00000000003f5e37 00000000ffffffff ffff880275471988 ffff88027545ff60
[    0.738320] Call Trace:
[    0.740772]  [<ffffffff810afda5>] find_busiest_group+0x45/0x480
[    0.746692]  [<ffffffff810b02da>] load_balance+0xfa/0x6e0
[    0.752084]  [<ffffffff810ae820>] ? active_load_balance_cpu_stop+0x1d0/0x1d0
[    0.759127]  [<ffffffff810b0c7c>] idle_balance+0xcc/0x130
[    0.764529]  [<ffffffff81530686>] __schedule+0x756/0x760
[    0.769829]  [<ffffffff81530749>] schedule+0x29/0x70
[    0.774795]  [<ffffffff8152ee45>] schedule_timeout+0x1b5/0x2e0
[    0.780623]  [<ffffffff8106986e>] ? physflat_send_IPI_mask+0xe/0x10
[    0.786885]  [<ffffffff810655e6>] ? native_smp_send_reschedule+0x46/0x60
[    0.793584]  [<ffffffff810a6fd0>] ? resched_task+0x60/0x70
[    0.799052]  [<ffffffff810a7565>] ? check_preempt_curr+0x75/0xa0
[    0.805051]  [<ffffffff8152fdb6>] wait_for_common+0xc6/0x160
[    0.810716]  [<ffffffff810aa420>] ? try_to_wake_up+0x2a0/0x2a0
[    0.816541]  [<ffffffff8152ff2d>] wait_for_completion+0x1d/0x20
[    0.822461]  [<ffffffff81099fe9>] kthread_create_on_node+0xa9/0x130
[    0.828714]  [<ffffffff8152ac86>] ? alternate_node_alloc+0x9d/0xa6
[    0.834890]  [<ffffffff81093cd0>] ? worker_maybe_bind_and_lock.isra.27+0xd0/0xd0
[    0.842266]  [<ffffffff81160201>] ? kmem_freepages.isra.41+0x91/0x150
[    0.848701]  [<ffffffff81095d2d>] __alloc_workqueue_key+0x1dd/0x3f0
[    0.854963]  [<ffffffff818c7d26>] ? sched_init_smp+0x300/0x30f
[    0.860787]  [<ffffffff818c9891>] cpuset_init_smp+0x40/0x50
[    0.866356]  [<ffffffff818b2c49>] kernel_init+0xb9/0x1ad
[    0.871662]  [<ffffffff8153a0d4>] kernel_thread_helper+0x4/0x10
[    0.877573]  [<ffffffff818b2b90>] ? start_kernel+0x37e/0x37e
[    0.883216]  [<ffffffff8153a0d0>] ? gs_change+0xb/0xb

This is

4ec4412e kernel/sched/fair.c 3876) if (local_group) {
bd939f45 kernel/sched/fair.c 3877) if (env->idle != CPU_NEWLY_IDLE) {
04f733b4 kernel/sched/fair.c 3878) if (balance_cpu != env->dst_cpu) {
4ec4412e kernel/sched/fair.c 3879) *balance = 0;
4ec4412e kernel/sched/fair.c 3880) return;
4ec4412e kernel/sched/fair.c 3881) }
bd939f45 kernel/sched/fair.c 3882) update_group_power(env->sd, env->dst_cpu);
4ec4412e kernel/sched/fair.c 3883) } else if (time_after_eq(jiffies, group->sgp->next_update))
bd939f45 kernel/sched/fair.c 3884) update_group_power(env->sd, env->dst_cpu);
1e3c88bd kernel/sched_fair.c 3885) }
1e3c88bd kernel/sched_fair.c 3886)
1e3c88bd kernel/sched_fair.c 3887) /* Adjust by relative CPU power of the group */
9c3f75cb kernel/sched_fair.c 3888) sgs->avg_load = (sgs->group_load*SCHED_POWER_SCALE) / group->sgp->power;

the divide of group->sgp->power. This doesn't happen when reverting back to sched/urgent at 30b4e9eb783d ("sched: Fix KVM and ia64 boot crash due to sched_groups circular linked list assumption"). Let me know if you'd like a bisect if the problem isn't immediately obvious.

I'm fairly sure you'll hit cb83b629b with your bisect (I've got one more report on this).

So the code in build_sched_domains() initializes the group->sgp->power stuff through init_sched_groups_power(), which ends up calling update_cpu_power() for every individual cpu and update_group_power() for groups.

Now update_cpu_power() should ensure ->power isn't ever 0 -- it sets it to 1 in that case, update_group_power() computes a straight sum of power, which being assumed are all >0 should also result in >0.

Only after we initialize the power in build_sched_domains() do we install the domains, so we should never hit the above.

Now clearly we do so there's a hole somewhere.. let me carefully read all that.

The below appears to contain a bug, not sure its the one you're triggering, but who knows. Lemme stare more.

---
Subject: sched: Make sure to not re-read variables after validation

We could re-read rq->rt_avg after we validated it was smaller than total, invalidating the check and resulting in an unintended negative.

---
 kernel/sched/fair.c |   15 +++++++++++----
 1 file changed, 11 insertions(+), 4 deletions(-)

index de49ed5..54dca4d 100644
@@ -3697,15 +3697,22 @@ unsigned long __weak arch_scale_smt_power(struct sched_domain *sd, int cpu)
 unsigned long scale_rt_power(int cpu)
 {
 	struct rq *rq = cpu_rq(cpu);
-	u64 total, available;
+	u64 total, available, age_stamp, avg;
 
-	total = sched_avg_period() + (rq->clock - rq->age_stamp);
+	/*
+	 * Since we're reading these variables without serialization make sure
+	 * we read them once before doing sanity checks on them.
+	 */
+	age_stamp = ACCESS_ONCE(rq->age_stamp);
+	avg = ACCESS_ONCE(rq->rt_avg);
+
+	total = sched_avg_period() + (rq->clock - age_stamp);
 
-	if (unlikely(total < rq->rt_avg)) {
+	if (unlikely(total < avg)) {
 		/* Ensures that power won't end up being negative */
 		available = 0;
 	} else {
-		available = total - rq->rt_avg;
+		available = total - avg;
 	}
 
 	if (unlikely((s64)total < SCHED_POWER_SCALE))

OK, nevermind that patch (not that it isn't a good one), but I've found the problem. build_overlap_sched_groups() is crummy.. just no idea how to go about fixing it quite yet though.

/me goes kick his gray cells some more.

OK, does the below make your machine happy? If not, please share the completely topology setup of that thing (lscpu or similar).

---
Subject: sched: Fix SD_OVERLAP

SD_OVERLAP exists to allow overlapping groups, overlapping groups appear in NUMA topologies that aren't fully connected.

The typical result of not fully connected NUMA is that each cpu (or rather node) will have different spans for a particular distance. However due to how sched domains are traversed -- only the first cpu in the mask goes one level up -- the next level only cares about the spans of the cpus that went up.

Due to this two things were observed to be broken:

- build_overlap_sched_groups() -- since its possible the cpu we're building the groups for exists in multiple (or all) groups, the selection criteria of the first group didn't ensure there was a cpu for which is was true that cpumask_first(span) == cpu. Thus load- balancing would terminate.

- update_group_power() -- assumed that the cpu span of the first group of the domain was covered by all groups of the child domain. The above explains why this isn't true, so deal with it.

---
 kernel/sched/core.c |    7 +++++--
 kernel/sched/fair.c |   25 ++++++++++++++++++++-----
 2 files changed, 25 insertions(+), 7 deletions(-)

index 18eed17..29217a4 100644
@@ -6007,11 +6007,14 @@ build_overlap_sched_groups(struct sched_domain *sd, int cpu)
 
 		cpumask_or(covered, covered, sg_span);
 
-		sg->sgp = *per_cpu_ptr(sdd->sgp, cpumask_first(sg_span));
+		sg->sgp = *per_cpu_ptr(sdd->sgp, i);
 		atomic_inc(&sg->sgp->ref);
 
-		if (cpumask_test_cpu(cpu, sg_span))
+		if ((!groups && cpumask_test_cpu(cpu, sg_span)) ||
+			       cpumask_first(sg_span) == cpu) {
+			WARN_ON_ONCE(!cpumask_test_cpu(cpu, sg_span));
 			groups = sg;
+		}
 
 		if (!first)
 			first = sg;

index de49ed5..7466b7a 100644
@@ -3768,11 +3768,26 @@ void update_group_power(struct sched_domain *sd, int cpu)
 
 	power = 0;
 
-	group = child->groups;
-	do {
-		power += group->sgp->power;
-		group = group->next;
-	} while (group != child->groups);
+	if (child->flags & SD_OVERLAP) {
+		/*
+		 * SD_OVERLAP domains cannot assume that child groups
+		 * span the current group.
+		 */
+
+		for_each_cpu(cpu, sched_group_cpus(sdg))
+			power += power_of(cpu);
+	} else  {
+		/*
+		 * !SD_OVERLAP domains can assume that child groups
+		 * span the current group.
+		 */ 
+
+		group = child->groups;
+		do {
+			power += group->sgp->power;
+			group = group->next;
+		} while (group != child->groups);
+	}
 
 	sdg->sgp->power = power;
 }

Same divide by zero. I'd be happy to run a debugging patch if you can come up with one.

$ grep -E 'processor|core|sibling|physical id|apicid|cpuid' /proc/cpuinfo | sed 's/processor/\nprocessor/'
processor	: 0
physical id	: 0
siblings	: 4
core id		: 0
cpu cores	: 4
apicid		: 4
initial apicid	: 0
cpuid level	: 5

processor : 1
physical id : 0
siblings : 4
core id : 1
cpu cores : 4
apicid : 5
initial apicid : 1
cpuid level : 5

processor : 2
physical id : 0
siblings : 4
core id : 2
cpu cores : 4
apicid : 6
initial apicid : 2
cpuid level : 5

processor : 3
physical id : 0
siblings : 4
core id : 3
cpu cores : 4
apicid : 7
initial apicid : 3
cpuid level : 5

processor : 4
physical id : 1
siblings : 4
core id : 0
cpu cores : 4
apicid : 8
initial apicid : 4
cpuid level : 5

processor : 5
physical id : 1
siblings : 4
core id : 1
cpu cores : 4
apicid : 9
initial apicid : 5
cpuid level : 5

processor : 6
physical id : 1
siblings : 4
core id : 2
cpu cores : 4
apicid : 10
initial apicid : 6
cpuid level : 5

processor : 7
physical id : 1
siblings : 4
core id : 3
cpu cores : 4
apicid : 11
initial apicid : 7
cpuid level : 5

processor : 8
physical id : 2
siblings : 4
core id : 0
cpu cores : 4
apicid : 12
initial apicid : 8
cpuid level : 5

processor : 9
physical id : 2
siblings : 4
core id : 1
cpu cores : 4
apicid : 13
initial apicid : 9
cpuid level : 5

processor : 10
physical id : 2
siblings : 4
core id : 2
cpu cores : 4
apicid : 14
initial apicid : 10
cpuid level : 5

processor : 11
physical id : 2
siblings : 4
core id : 3
cpu cores : 4
apicid : 15
initial apicid : 11
cpuid level : 5

processor : 12
physical id : 3
siblings : 4
core id : 0
cpu cores : 4
apicid : 16
initial apicid : 12
cpuid level : 5

processor : 13
physical id : 3
siblings : 4
core id : 1
cpu cores : 4
apicid : 17
initial apicid : 13
cpuid level : 5

processor : 14
physical id : 3
siblings : 4
core id : 2
cpu cores : 4
apicid : 18
initial apicid : 14
cpuid level : 5

processor : 15
physical id : 3
siblings : 4
core id : 3
cpu cores : 4
apicid : 19
initial apicid : 15
cpuid level : 5

Curious, that looks like a 4 socket 4 core machine without HT. Is this some Core2 era Xeon setup or so?

What does the node distance table on that thing look like?

cat /sys/devices/system/node/node*/distance

Anyway, could you boot that machine with

CONFIG_SCHED_DEBUG
CONFIG_FTRACE

and the following added to the boot parameters:

"sched_debug debug ftrace_dump_on_oops ftrace=nop"

that should dump the ftrace buffer (to which the trace_printk() stmts go) to the console when it explodes.

If you could then send me the complete console output (privately if its too big)..

NOTE this patch includes the previous patches so you should be able to apply it to a clean tree.

---
 arch/x86/mm/numa.c  |    6 ++----
 kernel/sched/core.c |   40 +++++++++++++++++++++++++++++++---------
 kernel/sched/fair.c |   50 +++++++++++++++++++++++++++++++++++++++++---------
 lib/vsprintf.c      |    5 +++++
 4 files changed, 79 insertions(+), 22 deletions(-)

index 19d3fa0..3f16071 100644
@@ -751,7 +751,6 @@ int early_cpu_to_node(int cpu)
 void debug_cpumask_set_cpu(int cpu, int node, bool enable)
 {
 	struct cpumask *mask;
-	char buf[64];
 
 	if (node == NUMA_NO_NODE) {
 		/* early_cpu_to_node() already emits a warning and trace */

@@ -769,10 +768,9 @@ void debug_cpumask_set_cpu(int cpu, int node, bool enable)
 	else
 		cpumask_clear_cpu(cpu, mask);
 
-	cpulist_scnprintf(buf, sizeof(buf), mask);
-	printk(KERN_DEBUG "%s cpu %d node %d: mask now %s\n",
+	printk(KERN_DEBUG "%s cpu %d node %d: mask now %pc\n",
 		enable ? "numa_add_cpu" : "numa_remove_cpu",
-		cpu, node, buf);
+		cpu, node, mask);
 	return;
 }
 

index 18eed17..eee020c 100644
@@ -5537,9 +5537,7 @@ static int sched_domain_debug_one(struct sched_domain *sd, int cpu, int level,
 				  struct cpumask *groupmask)
 {
 	struct sched_group *group = sd->groups;
-	char str[256];
 
-	cpulist_scnprintf(str, sizeof(str), sched_domain_span(sd));
 	cpumask_clear(groupmask);
 
 	printk(KERN_DEBUG "%*s domain %d: ", level, "", level);

@@ -5552,7 +5550,7 @@ static int sched_domain_debug_one(struct sched_domain *sd, int cpu, int level,
 		return -1;
 	}
 
-	printk(KERN_CONT "span %s level %s\n", str, sd->name);
+	printk(KERN_CONT "span %pc level %s\n", sched_domain_span(sd), sd->name);
 
 	if (!cpumask_test_cpu(cpu, sched_domain_span(sd))) {
 		printk(KERN_ERR "ERROR: domain->span does not contain "

@@ -5593,9 +5591,7 @@ static int sched_domain_debug_one(struct sched_domain *sd, int cpu, int level,
 
 		cpumask_or(groupmask, groupmask, sched_group_cpus(group));
 
-		cpulist_scnprintf(str, sizeof(str), sched_group_cpus(group));
-
-		printk(KERN_CONT " %s", str);
+		printk(KERN_CONT " %pc", sched_group_cpus(group));
 		if (group->sgp->power != SCHED_POWER_SCALE) {
 			printk(KERN_CONT " (cpu_power = %d)",
 				group->sgp->power);

@@ -6005,13 +6001,18 @@ build_overlap_sched_groups(struct sched_domain *sd, int cpu)
 		} else
 			cpumask_set_cpu(i, sg_span);
 
+		trace_printk("  group: cpu (%d) span (%pc)\n", cpu, sg_span);
+
 		cpumask_or(covered, covered, sg_span);
 
-		sg->sgp = *per_cpu_ptr(sdd->sgp, cpumask_first(sg_span));
+		sg->sgp = *per_cpu_ptr(sdd->sgp, i);
 		atomic_inc(&sg->sgp->ref);
 
-		if (cpumask_test_cpu(cpu, sg_span))
+		if ((!groups && cpumask_test_cpu(cpu, sg_span)) ||
+			       cpumask_first(sg_span) == cpu) {
+			WARN_ON_ONCE(!cpumask_test_cpu(cpu, sg_span));
 			groups = sg;
+		}
 
 		if (!first)
 			first = sg;

@@ -6125,6 +6126,9 @@ static void init_sched_groups_power(int cpu, struct sched_domain *sd)
 		sg = sg->next;
 	} while (sg != sd->groups);
 
+	trace_printk("groups init: cpu (%d) domain (%pc)\n", cpu,
+			sched_domain_span(sd));
+
 	if (cpu != group_first_cpu(sg))
 		return;
 

@@ -6421,6 +6425,7 @@ static void sched_init_numa(void)
 			sched_domains_numa_distance[level++] = next_distance;
 			sched_domains_numa_levels = level;
 			curr_distance = next_distance;
+			trace_printk("numa: found distance: %d\n", next_distance);
 		} else break;
 	}
 	/*

@@ -6446,7 +6451,7 @@ static void sched_init_numa(void)
 			return;
 
 		for (j = 0; j < nr_node_ids; j++) {
-			struct cpumask *mask = kzalloc_node(cpumask_size(), GFP_KERNEL, j);
+			struct cpumask *mask = kzalloc(cpumask_size(), GFP_KERNEL);
 			if (!mask)
 				return;
 

@@ -6458,6 +6463,9 @@ static void sched_init_numa(void)
 
 				cpumask_or(mask, mask, cpumask_of_node(k));
 			}
+
+			trace_printk("numa: level (%d) node (%d) mask (%pc)\n",
+					i, j, mask);
 		}
 	}
 

@@ -6484,6 +6492,8 @@ static void sched_init_numa(void)
 		};
 	}
 
+	trace_printk("numa: %d levels of numa goodness added!\n", j);
+
 	sched_domain_topology = tl;
 }
 #else

@@ -6621,6 +6631,8 @@ static int build_sched_domains(const struct cpumask *cpu_map,
 		sd = NULL;
 		for (tl = sched_domain_topology; tl->init; tl++) {
 			sd = build_sched_domain(tl, &d, cpu_map, attr, sd, i);
+			trace_printk("domain: cpu (%d) span (%pc)\n",
+					i, sched_domain_span(sd));
 			if (tl->flags & SDTL_OVERLAP || sched_feat(FORCE_SD_OVERLAP))
 				sd->flags |= SD_OVERLAP;
 			if (cpumask_equal(cpu_map, sched_domain_span(sd)))

@@ -6636,6 +6648,8 @@ static int build_sched_domains(const struct cpumask *cpu_map,
 	/* Build the groups for the domains */
 	for_each_cpu(i, cpu_map) {
 		for (sd = *per_cpu_ptr(d.sd, i); sd; sd = sd->parent) {
+			struct sched_group *sg;
+
 			sd->span_weight = cpumask_weight(sched_domain_span(sd));
 			if (sd->flags & SD_OVERLAP) {
 				if (build_overlap_sched_groups(sd, i))

@@ -6644,6 +6658,14 @@ static int build_sched_domains(const struct cpumask *cpu_map,
 				if (build_sched_groups(sd, i))
 					goto error;
 			}
+			
+			sg = sd->groups;
+			do {
+				trace_printk("groups: cpu (%d) domain (%pc) group (%pc)\n",
+						i, sched_domain_span(sd), 
+						sched_group_cpus(sg));
+				sg = sg->next;
+			} while (sg != sd->groups);
 		}
 	}
 

index abbabec..3b880ae 100644
@@ -25,6 +25,7 @@
 #include <linux/kallsyms.h>
 #include <linux/uaccess.h>
 #include <linux/ioport.h>
+#include <linux/cpumask.h>
 #include <net/addrconf.h>
 
 #include <asm/page.h>		/* for PAGE_SIZE */

@@ -857,6 +858,7 @@ int kptr_restrict __read_mostly;
  *       correctness of the format string and va_list arguments.
  * - 'K' For a kernel pointer that should be hidden from unprivileged users
  * - 'NF' For a netdev_features_t
+ * - 'c' For a cpumask list
  *
  * Note: The difference between 'S' and 'F' is that on ia64 and ppc64
  * function pointers are really function descriptors, which contain a

@@ -941,6 +943,8 @@ char *pointer(const char *fmt, char *buf, char *end, void *ptr,
 			return netdev_feature_string(buf, end, ptr, spec);
 		}
 		break;
+	case 'c':
+		return buf + cpulist_scnprintf(buf, end - buf, ptr);
 	}
 	spec.flags |= SMALL;
 	if (spec.field_width == -1) {

@@ -1175,6 +1179,7 @@ int format_decode(const char *fmt, struct printf_spec *spec)
  * %pI6c print an IPv6 address as specified by RFC 5952
  * %pU[bBlL] print a UUID/GUID in big or little endian using lower or upper
  *   case.
+ * %pc print a cpumask as comma-separated list
  * %n is ignored
  *
  * The return value is the number of characters which would

The below makes it boot and I think even balance right. But I'm not happy with the patch as I think it can be done simpler. The resulting domain setup isn't minimal either.

---
Subject:
From: Peter Zijlstra <[email protected]>
Date: Thu May 31 14:47:33 CEST 2012

---
 include/linux/sched.h |   11 ++++++++
 kernel/sched/core.c   |   64 +++++++++++++++++++++++++++++++++++++++++++-------
 kernel/sched/fair.c   |    5 ++-
 kernel/sched/sched.h  |    2 +
 4 files changed, 72 insertions(+), 10 deletions(-)

@@ -878,6 +878,8 @@ struct sched_group_power {
 	 * Number of busy cpus in this group.
 	 */
 	atomic_t nr_busy_cpus;
+
+	unsigned long cpumask[0]; /* iteration mask */
 };
 
 struct sched_group {

@@ -902,6 +904,15 @@ static inline struct cpumask *sched_grou
 	return to_cpumask(sg->cpumask);
 }
 
+/*
+ * cpumask masking which cpus in the group are allowed to iterate up the domain
+ * tree.
+ */
+static inline struct cpumask *sched_group_mask(struct sched_group *sg)
+{
+	return to_cpumask(sg->sgp->cpumask);
+}
+
 /**
  * group_first_cpu - Returns the first cpu in the cpumask of a sched_group.
  * @group: The group whose first cpu is to be returned.

@@ -3846,7 +3846,7 @@ static inline void update_sg_lb_stats(st
 	int i;
 
 	if (local_group)
-		balance_cpu = group_first_cpu(group);
+		balance_cpu = group_balance_cpu(group);
 
 	/* Tally up the load of all CPUs in the group */
 	max_cpu_load = 0;

@@ -3861,7 +3861,8 @@ static inline void update_sg_lb_stats(st
 
 		/* Bias balancing toward cpus of our domain */
 		if (local_group) {
-			if (idle_cpu(i) && !first_idle_cpu) {
+			if (idle_cpu(i) && !first_idle_cpu &&
+					cpumask_test_cpu(i, sched_group_mask(group))) {
 				first_idle_cpu = 1;
 				balance_cpu = i;
 			}

@@ -542,6 +542,8 @@ DECLARE_PER_CPU(struct sched_domain *, s
 DECLARE_PER_CPU(int, sd_llc_id);
 DECLARE_PER_CPU(struct sched_domain *, sd_node);
 
+extern int group_balance_cpu(struct sched_group *sg);
+
 #endif /* CONFIG_SMP */
 
 #include "stats.h"

Commit-ID:  74a5ce20e6eeeb3751340b390e7ac1d1d07bbf55
Gitweb:     http://git.kernel.org/tip/74a5ce20e6eeeb3751340b390e7ac1d1d07bbf55
Author:     Peter Zijlstra <[email protected]>
AuthorDate: Wed, 23 May 2012 18:00:43 +0200
Committer:  Ingo Molnar <[email protected]>
CommitDate: Wed, 30 May 2012 14:02:24 +0200

sched: Fix SD_OVERLAP

SD_OVERLAP exists to allow overlapping groups, overlapping groups appear in NUMA topologies that aren't fully connected.

The typical result of not fully connected NUMA is that each cpu (or rather node) will have different spans for a particular distance. However due to how sched domains are traversed -- only the first cpu in the mask goes one level up -- the next level only cares about the spans of the cpus that went up.

Due to this two things were observed to be broken:

- build_overlap_sched_groups() -- since its possible the cpu we're building the groups for exists in multiple (or all) groups, the selection criteria of the first group didn't ensure there was a cpu for which is was true that cpumask_first(span) == cpu. Thus load- balancing would terminate.

- update_group_power() -- assumed that the cpu span of the first group of the domain was covered by all groups of the child domain. The above explains why this isn't true, so deal with it.

---
 kernel/sched/core.c |    7 +++++--
 kernel/sched/fair.c |   25 ++++++++++++++++++++-----
 2 files changed, 25 insertions(+), 7 deletions(-)

index 5573361..3a69374 100644
@@ -6030,11 +6030,14 @@ build_overlap_sched_groups(struct sched_domain *sd, int cpu)
 
 		cpumask_or(covered, covered, sg_span);
 
-		sg->sgp = *per_cpu_ptr(sdd->sgp, cpumask_first(sg_span));
+		sg->sgp = *per_cpu_ptr(sdd->sgp, i);
 		atomic_inc(&sg->sgp->ref);
 
-		if (cpumask_test_cpu(cpu, sg_span))
+		if ((!groups && cpumask_test_cpu(cpu, sg_span)) ||
+			       cpumask_first(sg_span) == cpu) {
+			WARN_ON_ONCE(!cpumask_test_cpu(cpu, sg_span));
 			groups = sg;
+		}
 
 		if (!first)
 			first = sg;

index 940e6d1..f0380d4 100644
@@ -3574,11 +3574,26 @@ void update_group_power(struct sched_domain *sd, int cpu)
 
 	power = 0;
 
-	group = child->groups;
-	do {
-		power += group->sgp->power;
-		group = group->next;
-	} while (group != child->groups);
+	if (child->flags & SD_OVERLAP) {
+		/*
+		 * SD_OVERLAP domains cannot assume that child groups
+		 * span the current group.
+		 */
+
+		for_each_cpu(cpu, sched_group_cpus(sdg))
+			power += power_of(cpu);
+	} else  {
+		/*
+		 * !SD_OVERLAP domains can assume that child groups
+		 * span the current group.
+		 */ 
+
+		group = child->groups;
+		do {
+			power += group->sgp->power;
+			group = group->next;
+		} while (group != child->groups);
+	}
 
 	sdg->sgp->power = power;
 }

Commit-ID:  b654f7de41b0e3903ee2b51d3b8db77fe52ce728
Gitweb:     http://git.kernel.org/tip/b654f7de41b0e3903ee2b51d3b8db77fe52ce728
Author:     Peter Zijlstra <[email protected]>
AuthorDate: Tue, 22 May 2012 14:04:28 +0200
Committer:  Ingo Molnar <[email protected]>
CommitDate: Wed, 30 May 2012 14:02:24 +0200

sched: Make sure to not re-read variables after validation

We could re-read rq->rt_avg after we validated it was smaller than total, invalidating the check and resulting in an unintended negative.

---
 kernel/sched/fair.c |   15 +++++++++++----
 1 files changed, 11 insertions(+), 4 deletions(-)

index f0380d4..2b449a7 100644
@@ -3503,15 +3503,22 @@ unsigned long __weak arch_scale_smt_power(struct sched_domain *sd, int cpu)
 unsigned long scale_rt_power(int cpu)
 {
 	struct rq *rq = cpu_rq(cpu);
-	u64 total, available;
+	u64 total, available, age_stamp, avg;
 
-	total = sched_avg_period() + (rq->clock - rq->age_stamp);
+	/*
+	 * Since we're reading these variables without serialization make sure
+	 * we read them once before doing sanity checks on them.
+	 */
+	age_stamp = ACCESS_ONCE(rq->age_stamp);
+	avg = ACCESS_ONCE(rq->rt_avg);
+
+	total = sched_avg_period() + (rq->clock - age_stamp);
 
-	if (unlikely(total < rq->rt_avg)) {
+	if (unlikely(total < avg)) {
 		/* Ensures that power won't end up being negative */
 		available = 0;
 	} else {
-		available = total - rq->rt_avg;
+		available = total - avg;
 	}
 
 	if (unlikely((s64)total < SCHED_POWER_SCALE))