[patch] Re: Bug 619 - sched_best_cpu does not pick best cpu (1/2)

[patch] Re: Bug 619 - sched_best_cpu does not pick best cpu (1/2)

[Matthew Dobson]

[-- Attachment #1: Type: text/plain, Size: 888 bytes --]

This patch is in regard to bugme.osdl.org bug 619, link here:

http://bugme.osdl.org/show_bug.cgi?id=619

This is the first of two patches to fix this bug.  This patch changes 
the nine files that #include <asm/topology.h> to #include 
<linux/topology.h>.  It also creates include/linux/topology.h, but 
solely as a shell.  The next patch fills it in.

[mcd@arrakis src]$ diffstat ~/patches/add_linux_topo.patch
  drivers/base/cpu.c        |    3 +--
  drivers/base/memblk.c     |    3 +--
  drivers/base/node.c       |    3 +--
  include/asm-i386/cpu.h    |    2 +-
  include/asm-i386/memblk.h |    2 +-
  include/asm-i386/node.h   |    3 +--
  include/linux/mmzone.h    |    2 +-
  include/linux/topology.h  |   32 ++++++++++++++++++++++++++++++++
  mm/page_alloc.c           |    3 +--
  mm/vmscan.c               |    2 +-
  10 files changed, 41 insertions(+), 14 deletions(-)

-Matt

[-- Attachment #2: add_linux_topo.patch --]
[-- Type: text/plain, Size: 5853 bytes --]

diff -Nur --exclude-from=/home/mcd/.dontdiff linux-2.5.69-vanilla/drivers/base/cpu.c linux-2.5.69-add_linux_topo/drivers/base/cpu.c
--- linux-2.5.69-vanilla/drivers/base/cpu.c	Sun May  4 16:53:09 2003
+++ linux-2.5.69-add_linux_topo/drivers/base/cpu.c	Mon May  5 17:17:39 2003
@@ -6,8 +6,7 @@
 #include <linux/module.h>
 #include <linux/init.h>
 #include <linux/cpu.h>
-
-#include <asm/topology.h>
+#include <linux/topology.h>
 
 
 struct class cpu_class = {
diff -Nur --exclude-from=/home/mcd/.dontdiff linux-2.5.69-vanilla/drivers/base/memblk.c linux-2.5.69-add_linux_topo/drivers/base/memblk.c
--- linux-2.5.69-vanilla/drivers/base/memblk.c	Sun May  4 16:53:57 2003
+++ linux-2.5.69-add_linux_topo/drivers/base/memblk.c	Mon May  5 17:17:39 2003
@@ -7,8 +7,7 @@
 #include <linux/init.h>
 #include <linux/memblk.h>
 #include <linux/node.h>
-
-#include <asm/topology.h>
+#include <linux/topology.h>
 
 
 static struct class memblk_class = {
diff -Nur --exclude-from=/home/mcd/.dontdiff linux-2.5.69-vanilla/drivers/base/node.c linux-2.5.69-add_linux_topo/drivers/base/node.c
--- linux-2.5.69-vanilla/drivers/base/node.c	Sun May  4 16:53:02 2003
+++ linux-2.5.69-add_linux_topo/drivers/base/node.c	Mon May  5 17:17:39 2003
@@ -7,8 +7,7 @@
 #include <linux/init.h>
 #include <linux/mm.h>
 #include <linux/node.h>
-
-#include <asm/topology.h>
+#include <linux/topology.h>
 
 
 static struct class node_class = {
diff -Nur --exclude-from=/home/mcd/.dontdiff linux-2.5.69-vanilla/include/asm-i386/cpu.h linux-2.5.69-add_linux_topo/include/asm-i386/cpu.h
--- linux-2.5.69-vanilla/include/asm-i386/cpu.h	Sun May  4 16:53:35 2003
+++ linux-2.5.69-add_linux_topo/include/asm-i386/cpu.h	Mon May  5 17:17:39 2003
@@ -3,8 +3,8 @@
 
 #include <linux/device.h>
 #include <linux/cpu.h>
+#include <linux/topology.h>
 
-#include <asm/topology.h>
 #include <asm/node.h>
 
 struct i386_cpu {
diff -Nur --exclude-from=/home/mcd/.dontdiff linux-2.5.69-vanilla/include/asm-i386/memblk.h linux-2.5.69-add_linux_topo/include/asm-i386/memblk.h
--- linux-2.5.69-vanilla/include/asm-i386/memblk.h	Sun May  4 16:53:31 2003
+++ linux-2.5.69-add_linux_topo/include/asm-i386/memblk.h	Mon May  5 17:17:39 2003
@@ -4,8 +4,8 @@
 #include <linux/device.h>
 #include <linux/mmzone.h>
 #include <linux/memblk.h>
+#include <linux/topology.h>
 
-#include <asm/topology.h>
 #include <asm/node.h>
 
 struct i386_memblk {
diff -Nur --exclude-from=/home/mcd/.dontdiff linux-2.5.69-vanilla/include/asm-i386/node.h linux-2.5.69-add_linux_topo/include/asm-i386/node.h
--- linux-2.5.69-vanilla/include/asm-i386/node.h	Sun May  4 16:53:08 2003
+++ linux-2.5.69-add_linux_topo/include/asm-i386/node.h	Mon May  5 17:17:39 2003
@@ -4,8 +4,7 @@
 #include <linux/device.h>
 #include <linux/mmzone.h>
 #include <linux/node.h>
-
-#include <asm/topology.h>
+#include <linux/topology.h>
 
 struct i386_node {
 	struct node node;
diff -Nur --exclude-from=/home/mcd/.dontdiff linux-2.5.69-vanilla/include/linux/mmzone.h linux-2.5.69-add_linux_topo/include/linux/mmzone.h
--- linux-2.5.69-vanilla/include/linux/mmzone.h	Sun May  4 16:53:31 2003
+++ linux-2.5.69-add_linux_topo/include/linux/mmzone.h	Mon May  5 17:17:39 2003
@@ -255,7 +255,7 @@
 #define MAX_NR_MEMBLKS	1
 #endif /* CONFIG_NUMA */
 
-#include <asm/topology.h>
+#include <linux/topology.h>
 /* Returns the number of the current Node. */
 #define numa_node_id()		(cpu_to_node(smp_processor_id()))
 
diff -Nur --exclude-from=/home/mcd/.dontdiff linux-2.5.69-vanilla/include/linux/topology.h linux-2.5.69-add_linux_topo/include/linux/topology.h
--- linux-2.5.69-vanilla/include/linux/topology.h	Wed Dec 31 16:00:00 1969
+++ linux-2.5.69-add_linux_topo/include/linux/topology.h	Mon May  5 17:43:35 2003
@@ -0,0 +1,32 @@
+/*
+ * include/linux/topology.h
+ *
+ * Written by: Matthew Dobson, IBM Corporation
+ *
+ * Copyright (C) 2002, IBM Corp.
+ *
+ * All rights reserved.          
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE, GOOD TITLE or
+ * NON INFRINGEMENT.  See the GNU General Public License for more
+ * details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ *
+ * Send feedback to <colpatch@us.ibm.com>
+ */
+#ifndef _LINUX_TOPOLOGY_H
+#define _LINUX_TOPOLOGY_H
+
+#include <asm/topology.h>
+
+#endif /* _LINUX_TOPOLOGY_H */
diff -Nur --exclude-from=/home/mcd/.dontdiff linux-2.5.69-vanilla/mm/page_alloc.c linux-2.5.69-add_linux_topo/mm/page_alloc.c
--- linux-2.5.69-vanilla/mm/page_alloc.c	Sun May  4 16:53:01 2003
+++ linux-2.5.69-add_linux_topo/mm/page_alloc.c	Mon May  5 17:17:39 2003
@@ -28,8 +28,7 @@
 #include <linux/blkdev.h>
 #include <linux/slab.h>
 #include <linux/notifier.h>
-
-#include <asm/topology.h>
+#include <linux/topology.h>
 
 DECLARE_BITMAP(node_online_map, MAX_NUMNODES);
 DECLARE_BITMAP(memblk_online_map, MAX_NR_MEMBLKS);
diff -Nur --exclude-from=/home/mcd/.dontdiff linux-2.5.69-vanilla/mm/vmscan.c linux-2.5.69-add_linux_topo/mm/vmscan.c
--- linux-2.5.69-vanilla/mm/vmscan.c	Sun May  4 16:53:02 2003
+++ linux-2.5.69-add_linux_topo/mm/vmscan.c	Mon May  5 17:17:39 2003
@@ -28,10 +28,10 @@
 #include <linux/pagevec.h>
 #include <linux/backing-dev.h>
 #include <linux/rmap-locking.h>
+#include <linux/topology.h>
 
 #include <asm/pgalloc.h>
 #include <asm/tlbflush.h>
-#include <asm/topology.h>
 #include <asm/div64.h>
 
 #include <linux/swapops.h>

[patch] Re: Bug 619 - sched_best_cpu does not pick best cpu (2/2)

[Matthew Dobson]

[-- Attachment #1: Type: text/plain, Size: 756 bytes --]

This patch is in regard to bugme.osdl.org bug 619, link here:

http://bugme.osdl.org/show_bug.cgi?id=619

This is the second of two patches to fix this bug.  This patch fills in 
include/linux/topology.h (created in the last patch) with a couple 
#defines.  The patch also creates a generic_hweight64() in 
include/linux/bitops.h, which we've been lacking for a while.  It then 
uses these new macros in sched.c to ensure that if a node has no CPUs, 
it is not used in scheduling decisions.

[mcd@arrakis src]$ diffstat ~/patches/node_online.patch
  include/linux/bitops.h   |   27 +++++++++++++++++++++++++++
  include/linux/topology.h |    7 +++++++
  kernel/sched.c           |    2 +-
  3 files changed, 35 insertions(+), 1 deletion(-)

Cheers!

-Matt

[-- Attachment #2: node_online.patch --]
[-- Type: text/plain, Size: 2486 bytes --]

diff -Nur --exclude-from=/home/mcd/.dontdiff linux-2.5.69-add_linux_topo/include/linux/bitops.h linux-2.5.69-node_online_fix/include/linux/bitops.h
--- linux-2.5.69-add_linux_topo/include/linux/bitops.h	Sun May  4 16:53:42 2003
+++ linux-2.5.69-node_online_fix/include/linux/bitops.h	Mon May  5 18:00:00 2003
@@ -107,6 +107,33 @@
         return (res & 0x0F) + ((res >> 4) & 0x0F);
 }
 
+#if (BITS_PER_LONG == 64)
+
+static inline unsigned int generic_hweight64(unsigned int w)
+{
+        unsigned int res = (w & 0x5555555555555555) + ((w >> 1) & 0x5555555555555555);
+        res = (res & 0x3333333333333333) + ((res >> 2) & 0x3333333333333333);
+        res = (res & 0x0F0F0F0F0F0F0F0F) + ((res >> 4) & 0x0F0F0F0F0F0F0F0F);
+        res = (res & 0x00FF00FF00FF00FF) + ((res >> 8) & 0x00FF00FF00FF00FF);
+        res = (res & 0x0000FFFF0000FFFF) + ((res >> 16) & 0x0000FFFF0000FFFF);
+        return (res & 0x00000000FFFFFFFF) + ((res >> 32) & 0x00000000FFFFFFFF);
+}
+
+#define hweight_long(w)	generic_hweight64(w)
+
+#endif /* BITS_PER_LONG == 64 */
+
+#if (BITS_PER_LONG == 32)
+
+static inline unsigned int generic_hweight64(unsigned int *w)
+{
+	return generic_hweight32(w[0]) + generic_hweight32(w[1]);
+}
+
+#define hweight_long(w)	generic_hweight32(w)
+
+#endif /* BITS_PER_LONG == 32 */
+
 #include <asm/bitops.h>
 
 
diff -Nur --exclude-from=/home/mcd/.dontdiff linux-2.5.69-add_linux_topo/include/linux/topology.h linux-2.5.69-node_online_fix/include/linux/topology.h
--- linux-2.5.69-add_linux_topo/include/linux/topology.h	Mon May  5 17:43:35 2003
+++ linux-2.5.69-node_online_fix/include/linux/topology.h	Mon May  5 18:10:29 2003
@@ -27,6 +27,13 @@
 #ifndef _LINUX_TOPOLOGY_H
 #define _LINUX_TOPOLOGY_H
 
+#include <linux/bitops.h>
 #include <asm/topology.h>
 
+#define nr_cpus_node(node)	(hweight_long(node_to_cpumask(node)))
+
+#define for_each_node_with_cpus(node) \
+	for (node = 0; node < numnodes; node++) \
+		if (nr_cpus_node(node)
+
 #endif /* _LINUX_TOPOLOGY_H */
diff -Nur --exclude-from=/home/mcd/.dontdiff linux-2.5.69-add_linux_topo/kernel/sched.c linux-2.5.69-node_online_fix/kernel/sched.c
--- linux-2.5.69-add_linux_topo/kernel/sched.c	Sun May  4 16:53:37 2003
+++ linux-2.5.69-node_online_fix/kernel/sched.c	Mon May  5 18:10:58 2003
@@ -802,7 +802,7 @@
 		return best_cpu;
 
 	minload = 10000000;
-	for (i = 0; i < numnodes; i++) {
+	for_each_node_with_cpus(i) {
 		load = atomic_read(&node_nr_running[i]);
 		if (load < minload) {
 			minload = load;

Re: [patch] Re: Bug 619 - sched_best_cpu does not pick best cpu (2/2)

[David S. Miller]

On Mon, 2003-05-05 at 18:28, Matthew Dobson wrote:
> +#if (BITS_PER_LONG == 64)
> +
> +static inline unsigned int generic_hweight64(unsigned int w)
> +{
> +        unsigned int res = (w & 0x5555555555555555) + ((w >> 1) & 0x5555555555555555);

First, there is no way this works.  unsigned int doesn't
hold 64-bit values on any platform I know of. :-)

The best fix is to use 'u64' here and also to remove the silly
BITS_PER_LONG ifdef, it should always be available even on 32-bit
platforms.

-- 
David S. Miller <davem@redhat.com>

Re: [patch] Re: Bug 619 - sched_best_cpu does not pick best cpu (2/2)

[Gabriel Paubert]

On Mon, May 05, 2003 at 06:28:34PM -0700, Matthew Dobson wrote:
> This patch is in regard to bugme.osdl.org bug 619, link here:
> 
> http://bugme.osdl.org/show_bug.cgi?id=619
> 
> This is the second of two patches to fix this bug.  This patch fills in 
> include/linux/topology.h (created in the last patch) with a couple 
> #defines.  The patch also creates a generic_hweight64() in 
> include/linux/bitops.h, which we've been lacking for a while.  It then 
> uses these new macros in sched.c to ensure that if a node has no CPUs, 
> it is not used in scheduling decisions.
> 
> [mcd@arrakis src]$ diffstat ~/patches/node_online.patch
>  include/linux/bitops.h   |   27 +++++++++++++++++++++++++++
>  include/linux/topology.h |    7 +++++++
>  kernel/sched.c           |    2 +-
>  3 files changed, 35 insertions(+), 1 deletion(-)
> 
> Cheers!
> 
> -Matt

> diff -Nur --exclude-from=/home/mcd/.dontdiff linux-2.5.69-add_linux_topo/include/linux/bitops.h linux-2.5.69-node_online_fix/include/linux/bitops.h
> --- linux-2.5.69-add_linux_topo/include/linux/bitops.h	Sun May  4 16:53:42 2003
> +++ linux-2.5.69-node_online_fix/include/linux/bitops.h	Mon May  5 18:00:00 2003
> @@ -107,6 +107,33 @@
>          return (res & 0x0F) + ((res >> 4) & 0x0F);
>  }
>  
> +#if (BITS_PER_LONG == 64)
> +
> +static inline unsigned int generic_hweight64(unsigned int w)
> +{
> +        unsigned int res = (w & 0x5555555555555555) + ((w >> 1) & 0x5555555555555555);

Ignoring the fact that the types are wrong for 64 bit values, you can save
one masking (in all generic_hweight functions in fact) by using the
following expression for the first line:

	uxx res = w - ((w>>1) & 0x55...55);

where xx is 8, 16, 32, or 64 and the right number of 5s.
That's an old trick but I can't remember the reference nor
where I found the reference to it, sorry.

	Gabriel

[patch] Re: Bug 619 - sched_best_cpu does not pick best cpu (1/1)

[Andrew Theurer]

I believe this will work for ppc64:

[root@hearse root]#   diffstat patch-nr_cpus_node-ppc64-2.5.69
 arch/ppc64/mm/numa.c         |    6 +++++-
 include/asm-ppc64/mmzone.h   |    1 +
 include/asm-ppc64/topology.h |    5 +++++
 3 files changed, 11 insertions(+), 1 deletion(-)


diff -Naur 2.5.69-bk-5-8-2003-numa/arch/ppc64/mm/numa.c 
2.5.69-bk-5-8-2003-numa-nrcpusnode/arch/ppc64/mm/numa.c
--- 2.5.69-bk-5-8-2003-numa/arch/ppc64/mm/numa.c	2003-05-14 18:11:35.000000000 
-0700
+++ 2.5.69-bk-5-8-2003-numa-nrcpusnode/arch/ppc64/mm/numa.c	2003-05-14 
18:18:06.000000000 -0700
@@ -25,6 +25,7 @@
 int numa_memory_lookup_table[MAX_MEMORY >> MEMORY_INCREMENT_SHIFT] =
 	{ [ 0 ... ((MAX_MEMORY >> MEMORY_INCREMENT_SHIFT) - 1)] = -1};
 unsigned long numa_cpumask_lookup_table[MAX_NUMNODES];
+int nr_cpus_in_node[MAX_NUMNODES] = { [0 ... (MAX_NUMNODES -1)] = 0};
 
 struct pglist_data node_data[MAX_NUMNODES];
 bootmem_data_t plat_node_bdata[MAX_NUMNODES];
@@ -33,7 +34,10 @@
 {
 	dbg("cpu %d maps to domain %d\n", cpu, node);
 	numa_cpu_lookup_table[cpu] = node;
-	numa_cpumask_lookup_table[node] |= 1UL << cpu;
+	if (!(numa_cpumask_lookup_table[node] & 1UL << cpu)) {
+		numa_cpumask_lookup_table[node] |= 1UL << cpu;
+		nr_cpus_in_node[node]++;
+	}
 }
 
 static int __init parse_numa_properties(void)
diff -Naur 2.5.69-bk-5-8-2003-numa/include/asm-ppc64/mmzone.h 
2.5.69-bk-5-8-2003-numa-nrcpusnode/include/asm-ppc64/mmzone.h
--- 2.5.69-bk-5-8-2003-numa/include/asm-ppc64/mmzone.h	2003-04-24 
14:17:14.000000000 -0700
+++ 2.5.69-bk-5-8-2003-numa-nrcpusnode/include/asm-ppc64/mmzone.h	2003-05-14 
18:07:35.000000000 -0700
@@ -21,6 +21,7 @@
 extern int numa_cpu_lookup_table[];
 extern int numa_memory_lookup_table[];
 extern unsigned long numa_cpumask_lookup_table[];
+extern int nr_cpus_in_node[];
 
 #define MAX_MEMORY (1UL << 41)
 /* 256MB regions */
diff -Naur 2.5.69-bk-5-8-2003-numa/include/asm-ppc64/topology.h 
2.5.69-bk-5-8-2003-numa-nrcpusnode/include/asm-ppc64/topology.h
--- 2.5.69-bk-5-8-2003-numa/include/asm-ppc64/topology.h	2003-05-14 
11:03:10.000000000 -0700
+++ 2.5.69-bk-5-8-2003-numa-nrcpusnode/include/asm-ppc64/topology.h	2003-05-14 
18:08:38.000000000 -0700
@@ -6,6 +6,11 @@
 
 #ifdef CONFIG_NUMA
 
+static inline int nr_cpus_node(int node)
+{
+	return nr_cpus_in_node[node];
+}
+
 static inline int cpu_to_node(int cpu)
 {
 	int node;

Re: [patch] Re: Bug 619 - sched_best_cpu does not pick best cpu (1/1)

[Zwane Mwaikambo]

On Wed, 14 May 2003, Andrew Theurer wrote:

> +int nr_cpus_in_node[MAX_NUMNODES] = { [0 ... (MAX_NUMNODES -1)] = 0};
[snip...]
> +static inline int nr_cpus_node(int node)
> +{
> +	return nr_cpus_in_node[node];
> +}
> +
>  static inline int cpu_to_node(int cpu)
>  {
>  	int node;

How about an hweight() on node_to_cpumask?

	Zwane
-- 
function.linuxpower.ca

Re: [patch] Re: Bug 619 - sched_best_cpu does not pick best cpu (1/1)

[Andrew Theurer]

On Wednesday 14 May 2003 20:26, Zwane Mwaikambo wrote:
> On Wed, 14 May 2003, Andrew Theurer wrote:
> > +int nr_cpus_in_node[MAX_NUMNODES] = { [0 ... (MAX_NUMNODES -1)] = 0};
>
> [snip...]
>
> > +static inline int nr_cpus_node(int node)
> > +{
> > +	return nr_cpus_in_node[node];
> > +}
> > +
> >  static inline int cpu_to_node(int cpu)
> >  {
> >  	int node;
>
> How about an hweight() on node_to_cpumask?

I'd rather cache it.  I believe hweight() will be the asm-generic routine.

-Andrew