Skip to contentSkip to conversation

nodemask_t x86_64 changes [5/7]

PATCH In review Matthew Dobson 4 participants 13 messages Mar 18, 2004 – Mar 29, 2004 Generic include/asm header files

lore
Share & tools
lore

Matthew Dobson

author
#0 lore raw

PATCH 1/1 nodemask_t x86_64 changes [5/7]

nodemask_t-05-x86_64.patch - Changes to x86_64 specific code. Untested. Code review & testing requested.

arch/x86_64/kernel/setup64.c +3 -3
diff -Nurp --exclude-from=/home/mcd/.dontdiff linux-2.6.4-vanilla/arch/x86_64/kernel/setup64.c linux-2.6.4-nodemask_t-x86_64/arch/x86_64/kernel/setup64.c
@@ -135,11 +135,11 @@ void __init setup_per_cpu_areas(void)
 		unsigned char *ptr;
 		/* If possible allocate on the node of the CPU.
 		   In case it doesn't exist round-robin nodes. */
-		if (!NODE_DATA(i % numnodes)) { 
-			printk("cpu with no node %d, numnodes %d\n", i, numnodes);
+		if (!NODE_DATA(i % num_online_nodes())) { 
+			printk("cpu with no node %d, num_online_nodes() %d\n", i, num_online_nodes());
 			ptr = alloc_bootmem(size);
 		} else { 
-			ptr = alloc_bootmem_node(NODE_DATA(i % numnodes), size);
+			ptr = alloc_bootmem_node(NODE_DATA(i % num_online_nodes()), size);
 		}
 		if (!ptr)
 			panic("Cannot allocate cpu data for CPU %d\n", i);
arch/x86_64/mm/k8topology.c +15 -15
diff -Nurp --exclude-from=/home/mcd/.dontdiff linux-2.6.4-vanilla/arch/x86_64/mm/k8topology.c linux-2.6.4-nodemask_t-x86_64/arch/x86_64/mm/k8topology.c
@@ -44,7 +44,7 @@ static __init int find_northbridge(void)
 int __init k8_scan_nodes(unsigned long start, unsigned long end)
 { 
 	unsigned long prevbase;
-	struct node nodes[MAXNODE];
+	struct node nodes[MAX_NUMNODES];
 	int nodeid, i, nb; 
 	int found = 0;
 	u32 reg;

@@ -57,9 +57,10 @@ int __init k8_scan_nodes(unsigned long s
 	printk(KERN_INFO "Scanning NUMA topology in Northbridge %d\n", nb); 
 
 	reg = read_pci_config(0, nb, 0, 0x60); 
-	numnodes =  ((reg >> 4) & 7) + 1; 
+	for(i = 0; i <= ((reg >> 4) & 7); i++)
+		node_set_online(i); 
 
-	printk(KERN_INFO "Number of nodes %d (%x)\n", numnodes, reg);
+	printk(KERN_INFO "Number of nodes %d (%x)\n", num_online_nodes(), reg);
 
 	memset(&nodes,0,sizeof(nodes)); 
 	prevbase = 0;

@@ -71,11 +72,11 @@ int __init k8_scan_nodes(unsigned long s
 
 		nodeid = limit & 7; 
 		if ((base & 3) == 0) { 
-			if (i < numnodes) 
+			if (i < num_online_nodes()) 
 				printk("Skipping disabled node %d\n", i); 
 			continue;
 		} 
-		if (nodeid >= numnodes) { 
+		if (nodeid >= num_online_nodes()) { 
 			printk("Ignoring excess node %d (%lx:%lx)\n", nodeid,
 			       base, limit); 
 			continue;

@@ -91,7 +92,7 @@ int __init k8_scan_nodes(unsigned long s
 			       nodeid, (base>>8)&3, (limit>>8) & 3); 
 			return -1; 
 		}	
-		if ((1UL << nodeid) & nodes_present) { 
+		if (node_online(nodeid)) {
 			printk(KERN_INFO "Node %d already present. Skipping\n", 
 			       nodeid);
 			continue;

@@ -151,7 +152,7 @@ int __init k8_scan_nodes(unsigned long s
 	} 
 	printk(KERN_INFO "Using node hash shift of %d\n", memnode_shift); 
 
-	for (i = 0; i < MAXNODE; i++) { 
+	for_each_node(i) {
 		if (nodes[i].start != nodes[i].end)
 		setup_node_bootmem(i, nodes[i].start, nodes[i].end); 
 	} 

@@ -161,15 +162,14 @@ int __init k8_scan_nodes(unsigned long s
 	   mapping. To avoid this fill in the mapping for all possible
 	   CPUs, as the number of CPUs is not known yet. 
 	   We round robin the existing nodes. */
-	rr = 0;
-	for (i = 0; i < MAXNODE; i++) {
-		if (nodes_present & (1UL<<i))
-			continue;
-		if ((nodes_present >> rr) == 0) 
-			rr = 0; 
-		rr = ffz(~nodes_present >> rr); 
+	rr = first_node(node_online_map);
+	nodemask_t node_offline_map = nodes_complement(node_online_map);
+	for_each_node_mask(i, node_offline_map) {
 		node_data[i] = node_data[rr];
-		rr++; 
+
+		rr = next_node(rr, node_online_map);
+		if (rr >= MAX_NUMNODES)
+			rr = first_node(node_online_map);
 	}
 
 	if (found == 1)
arch/x86_64/mm/numa.c +6 -10
diff -Nurp --exclude-from=/home/mcd/.dontdiff linux-2.6.4-vanilla/arch/x86_64/mm/numa.c linux-2.6.4-nodemask_t-x86_64/arch/x86_64/mm/numa.c
@@ -16,7 +16,7 @@
 
 #define Dprintk(x...)
 
-struct pglist_data *node_data[MAXNODE];
+struct pglist_data *node_data[MAX_NUMNODES];
 bootmem_data_t plat_node_bdata[MAX_NUMNODES];
 
 int memnode_shift;

@@ -24,8 +24,6 @@ u8  memnodemap[NODEMAPSIZE];
 
 static int numa_off __initdata; 
 
-unsigned long nodes_present; 
-
 int __init compute_hash_shift(struct node *nodes)
 {
 	int i; 

@@ -35,7 +33,7 @@ int __init compute_hash_shift(struct nod
 	/* When in doubt use brute force. */
 	while (shift < 48) { 
 		memset(memnodemap,0xff,sizeof(*memnodemap) * NODEMAPSIZE); 
-		for (i = 0; i < numnodes; i++) { 
+		for_each_online_node(i) {
 			if (nodes[i].start == nodes[i].end) 
 				continue;
 			for (addr = nodes[i].start; 

@@ -101,9 +99,6 @@ void __init setup_node_bootmem(int nodei
 
 	reserve_bootmem_node(NODE_DATA(nodeid), nodedata_phys, pgdat_size); 
 	reserve_bootmem_node(NODE_DATA(nodeid), bootmap_start, bootmap_pages<<PAGE_SHIFT);
-	if (nodeid + 1 > numnodes)
-		numnodes = nodeid + 1;
-	nodes_present |= (1UL << nodeid); 
 	node_set_online(nodeid);
 } 
 

@@ -152,7 +147,8 @@ int __init numa_initmem_init(unsigned lo
 	fake_node = 1; 	
 	memnode_shift = 63; 
 	memnodemap[0] = 0;
-	numnodes = 1;
+	nodes_clear(node_online_map);
+	node_set_online(0);
 	setup_node_bootmem(0, start_pfn<<PAGE_SHIFT, end_pfn<<PAGE_SHIFT);
 	return -1; 
 } 

@@ -161,7 +157,7 @@ unsigned long __init numa_free_all_bootm
 { 
 	int i;
 	unsigned long pages = 0;
-	for_all_nodes(i) {
+	for_each_online_node(i) {
 		pages += free_all_bootmem_node(NODE_DATA(i));
 	}
 	return pages;

@@ -170,7 +166,7 @@ unsigned long __init numa_free_all_bootm
 void __init paging_init(void)
 { 
 	int i;
-	for_all_nodes(i) { 
+	for_each_online_node(i) { 
 		setup_node_zones(i); 
 	}
 }
include/asm-x86_64/mmzone.h +0 -1
diff -Nurp --exclude-from=/home/mcd/.dontdiff linux-2.6.4-vanilla/include/asm-x86_64/mmzone.h linux-2.6.4-nodemask_t-x86_64/include/asm-x86_64/mmzone.h
@@ -12,7 +12,6 @@
 
 #include <asm/smp.h>
 
-#define MAXNODE 8 
 #define NODEMAPSIZE 0xff
 
 /* Simple perfect hash to map physical addresses to node numbers */
include/asm-x86_64/numa.h +0 -6
diff -Nurp --exclude-from=/home/mcd/.dontdiff linux-2.6.4-vanilla/include/asm-x86_64/numa.h linux-2.6.4-nodemask_t-x86_64/include/asm-x86_64/numa.h
@@ -1,19 +1,13 @@
 #ifndef _ASM_X8664_NUMA_H 
 #define _ASM_X8664_NUMA_H 1
 
-#define MAXNODE 8 
 #define NODEMASK 0xff
 
 struct node { 
 	u64 start,end; 
 };
 
-#define for_all_nodes(x) for ((x) = 0; (x) < numnodes; (x)++) \
-				if ((1UL << (x)) & nodes_present)
-
-
 extern int compute_hash_shift(struct node *nodes);
-extern unsigned long nodes_present;
 
 #define ZONE_ALIGN (1UL << (MAX_ORDER+PAGE_SHIFT))
#1 lore raw

I'll be surprised if the following line works:

	nodemask_t node_offline_map = nodes_complement(node_online_map);

1) Doesn't nodes_complement return void, and work in place?
2) It might set bits above MAX_NUMNODES, if MAX_NUMNODES isn't a word size multiple.

I am less sure of (2) - the exact details of handling the unused bits of a bitmask are still confusing me. But this would be one of the very rare situations that I can find that would actually be sensitive to possible confusions here - most places don't set bits that aren't already set in some mask, or are careful to initialize a mask with just set bits in select positions from 0 to MAX_NUMNODES-1.

Signature · 3 lines
                          I won't rest till it's the best ...
                          Programmer, Linux Scalability
                          Paul Jackson <[email protected]> 1.650.933.1373
#2 lore raw
Quoted 10 lines · Paul Jackson

I'll be surprised if the following line works:

	nodemask_t node_offline_map = nodes_complement(node_online_map);

1) Doesn't nodes_complement return void, and work in place?
2) It might set bits above MAX_NUMNODES, if MAX_NUMNODES isn't a word size multiple. I am less sure of (2) - the exact details of handling the unused bits of a bitmask are still confusing me. But this would be one of the very rare situations that I can find that would actually be sensitive to possible confusions here - most places don't set bits that aren't already set in some mask, or are careful to initialize a mask with just set bits in select positions from 0 to MAX_NUMNODES-1.

In general I attempted to model things after 3-address code. bitmap_complement() is a glaring inconsistency I wouldn't mind seeing shored up with the rest (though I guess it's only got 2 operands).

-- wli

#3 lore raw

Yes - making the *_complement ops into two operand (dst, src) would be a good idea, Bill. Thanks. I will likely include that in what I'm doing now.

Meanwhile, Matthew's patch 5/7 appears broken here.

My current understanding of the complement op is that it is broken for non-word multiple sizes. There's a good chance I'm still be confused on this matter.

It might make sense to redo this particular bit of offline logic not by using *_complement, but rather by looping over all nodes, and only acting if not online, thus avoiding the *_complement() operator for now. I have not thought through the performance implications of such a code inversion, however.

Signature · 3 lines
                          I won't rest till it's the best ...
                          Programmer, Linux Scalability
                          Paul Jackson <[email protected]> 1.650.933.1373
#4 lore raw
Quoted 8 lines · Paul Jackson

My current understanding of the complement op is that it is broken for non-word multiple sizes. There's a good chance I'm still be confused on this matter.
It might make sense to redo this particular bit of offline logic not by using *_complement, but rather by looping over all nodes, and only acting if not online, thus avoiding the *_complement() operator for now. I have not thought through the performance implications of such a code inversion, however.

If someone's not treating the leftover bits as "don't cares", then there's a bug. Or so goes the current convention. I think originally, I had avoided touching the bits at the end, then the "don't cares" suggestion was incorporated). This doesn't appear to be problematic on smaller systems. Any idea where this bogon might be?

-- wli

#5 lore raw
Quoted 1 line

Any idea where this bogon might be?

Unless I'm missing something (quite possible), the following would expose the complement operators setting of high unused bits.

You have 32 bit unsigned longs and NR_CPUS == 24, you complement some cpumask, and you then ask if it is empty, or ask if it is equal to another cpumask that differs only in the unused high byte, or ask its Hamming weight?

The arithmetic cpumask ops don't mask off the unused bits above NR_CPUS.

This might never be noticed, because cpumask_complement is the only op that sets these unused bits, the complement op is very rarely used, and none of its current uses can lead to the above bugs that I see offhand.

My workarea (vanilla 2.6.4 plus Matthew's nodemask patch) right now has:

1) this complement operator entirely removed
2) its rare uses recoded to not use that op

I'm also experimenting with adding a precondition to each operation, that no bits above the specified size (NR_CPUS or whatever the equivalent for NODES is) may be set on input mask arguments. Each operation need do just enough to avoid setting any such unused high bits of output masks, given the assumption that they aren't already set on any input parameters.

With this precondition, operations need make no promise to avoid being confused by such high bits if improperly set on an input. They make no promise to mask off such bits in a result mask if passed in. Nor do they promise not to mask them off - that's at the discretion of the implementation.

This precondition actually fits the existing implementation quite well. About all I'd have to do, that I see so far, is to add code to the complement op to zero out the unused bits. Or just get rid of the complement op entirely ... as I'm considering.

Ah - one other place needs fixing - the array cpumask CPU_MASK_ALL initializer sets all bits, which is ok now, since the other array ops more or less all limit their considerations to the first NR_CPUS bits. But it wouldn't surprise me if someday a bug showed up here as well, added in the future perhaps, in the case that NR_CPUS is not an exact multiple of unsigned longs.

I still don't know how I will fix the CPU_MASK_ALL static initializor in the multi-word case - since I can't put runtime code in it.

Signature · 3 lines
                          I won't rest till it's the best ...
                          Programmer, Linux Scalability
                          Paul Jackson <[email protected]> 1.650.933.1373
#6 lore raw
Quoted 1 line · At some point in the past, I wrote:
Quoted 1 line

Any idea where this bogon might be?

Quoted 10 lines · Paul Jackson

Unless I'm missing something (quite possible), the following would expose the complement operators setting of high unused bits.
You have 32 bit unsigned longs and NR_CPUS == 24, you complement some cpumask, and you then ask if it is empty, or ask if it is equal to another cpumask that differs only in the unused high byte, or ask its Hamming weight?
The arithmetic cpumask ops don't mask off the unused bits above NR_CPUS. This might never be noticed, because cpumask_complement is the only op that sets these unused bits, the complement op is very rarely used, and none of its current uses can lead to the above bugs that I see offhand.

It's supposed to do this. bitmap_weight() masks off the trailing bits to filter out "don't cares" from whole-word ops. Everything else operates bitwise. Something like the following will keep the bits clear as you wish, since apparently the more simplistic single-word ops aren't obeying this. It's likely possible to better this by exploiting some invariants; feel free improve on it.

-- wli

include/asm-generic/cpumask_arith.h +14 -6
Index: pgcl-2.6.5-rc2/include/asm-generic/cpumask_arith.h
===================================================================
@@ -6,6 +6,12 @@
  * to contain the whole cpu bitmap.
  */
 
+#if NR_CPUS % BITS_PER_LONG
+#define __CPU_MASK_VALID_BITS__		((1UL << (NR_CPUS % BITS_PER_LONG)) - 1)
+#else
+#define __CPU_MASK_VALID_BITS__		(~0UL)
+#endif
+
 #define cpu_set(cpu, map)		set_bit(cpu, &(map))
 #define cpu_clear(cpu, map)		clear_bit(cpu, &(map))
 #define cpu_isset(cpu, map)		test_bit(cpu, &(map))

@@ -14,15 +20,15 @@
 #define cpus_and(dst,src1,src2)		do { dst = (src1) & (src2); } while (0)
 #define cpus_or(dst,src1,src2)		do { dst = (src1) | (src2); } while (0)
 #define cpus_clear(map)			do { map = 0; } while (0)
-#define cpus_complement(map)		do { map = ~(map); } while (0)
-#define cpus_equal(map1, map2)		((map1) == (map2))
-#define cpus_empty(map)			((map) == 0)
+#define cpus_complement(map)		do { map = ~(map) & __CPU_MASK_VALID_BITS__; } while (0)
+#define cpus_equal(map1, map2)		(!(((map1) ^ (map2)) & __CPU_MASK_VALID_BITS__))
+#define cpus_empty(map)			(!((map) & __CPU_MASK_VALID_BITS__))
 #define cpus_addr(map)			(&(map))
 
 #if BITS_PER_LONG == 32
-#define cpus_weight(map)		hweight32(map)
+#define cpus_weight(map)		hweight32((map) & __CPU_MASK_VALID_BITS__)
 #elif BITS_PER_LONG == 64
-#define cpus_weight(map)		hweight64(map)
+#define cpus_weight(map)		hweight64((map) & __CPU_MASK_VALID_BITS__)
 #endif
 
 #define cpus_shift_right(dst, src, n)	do { dst = (src) >> (n); } while (0)

@@ -39,11 +45,13 @@
 #define CPU_MASK_NONE	((cpumask_t)0)
 
 /* only ever use this for things that are _never_ used on large boxen */
-#define cpus_coerce(map)		((unsigned long)(map))
+#define cpus_coerce(map)		((unsigned long)(map) & __CPU_MASK_VALID_BITS__)
 #define cpus_promote(map)		({ map; })
 #define cpumask_of_cpu(cpu)		({ ((cpumask_t)1) << (cpu); })
 
 #define first_cpu(map)			__ffs(map)
 #define next_cpu(cpu, map)		find_next_bit(&(map), NR_CPUS, cpu + 1)
 
+#undef __CPU_MASK_VALID_BITS__
+
 #endif /* __ASM_GENERIC_CPUMASK_ARITH_H */
#7 lore raw
In reply to Paul Jackson
Quoted 2 lines · Paul Jackson

I still don't know how I will fix the CPU_MASK_ALL static initializor in the multi-word case - since I can't put runtime code in it.

#define NR_CPUS_WORDS ((NR_CPUS+BITS_PER_LONG-1)/BITS_PER_LONG) #define NR_CPUS_UNDEF (NR_CPUS_WORDS*BITS_PER_LONG-NR_CPUS)

#if NR_CPUS_UNDEF == 0
#define CPU_MASK_ALL { [0 ... NR_CPUS_WORDS-1] = ~0UL }
#else
#define CPU_MASK_ALL { [0 ... NR_CPUS_WORDS-2] = ~0UL, ~0UL << NR_CPUS_UNDEF } #endif

#8 lore raw
Quoted 1 line

CPU_MASK_ALL ...

Yup - now you tell me ... ;).

I just got done figuring it out in a slightly variant way ... ('nbits' is NR_CPUS or similar):

#define MASK_LAST_WORD(nbits)                                           \
(                                                                       \
        ((nbits) % BITS_PER_LONG) ?                                     \
                (1<<((nbits) % BITS_PER_LONG))-1 : ~0UL                 \

)

#define MASK_ALL(nbits)                                                 \
{ {                                                                     \
        [0 ... BITS_TO_LONGS(nbits)-1] = ~0UL,                          \
        [BITS_TO_LONGS(nbits)-1] = MASK_LAST_WORD(nbits)                \

} }

This way overwrites the last word of the mask, first putting ~0UL in all words, then however many bits are needed in the last word.

Does your way work if NR_CPUS is less than BITS_PER_LONG? Won't gcc complain upon seeing something like, for say NR_CPUS = 4 on a 32 bit system:

{ [ 0 ... -1 ] = ~0UL, ~0UL << 28 }

with the errors and warnings:

error: empty index range in initializer
warning: excess elements in struct initializer

and shouldn't the last word be inverted: ~(~0UL << NR_CPUS_UNDEF) ?

Signature · 3 lines
                          I won't rest till it's the best ...
                          Programmer, Linux Scalability
                          Paul Jackson <[email protected]> 1.650.933.1373
#9 lore raw
Quoted 10 lines · Paul Jackson

Does your way work if NR_CPUS is less than BITS_PER_LONG? Won't gcc complain upon seeing something like, for say NR_CPUS = 4 on a 32 bit system:

{ [ 0 ... -1 ] = ~0UL, ~0UL << 28 }

with the errors and warnings:

error: empty index range in initializer
warning: excess elements in struct initializer

I only did one case, to concentrate on the value for the last word. A full implementation has to cater for NR_CPUS < BITS_PER_LONG as well.

Quoted 1 line

and shouldn't the last word be inverted: ~(~0UL << NR_CPUS_UNDEF) ?

For big endian, ~0UL << NR_CPUS_UNDEF is right. For little endian, it depends on how you represent an incomplete bit map. Is it represented as a pure bit string, i.e. as if the arch were big endian? Or is it represented as a mapping onto the bytes of the underlying long?

#10 lore raw
Quoted 1 line

how you represent an incomplete bit map

See the follow files for the best available documentation of how bitmaps are layed out. The representation is little-endian friendly, so the big-endian arch's had to struggle with it the most, and ended up documenting it the best.

	include/asm-ppc64/bitops.h
	include/asm-s390/bitops.h
Signature · 3 lines
                          I won't rest till it's the best ...
                          Programmer, Linux Scalability
                          Paul Jackson <[email protected]> 1.650.933.1373
#11 lore raw
In reply to Keith Owens
Quoted 4 lines · Keith Owens

For big endian, ~0UL << NR_CPUS_UNDEF is right. For little endian, it depends on how you represent an incomplete bit map. Is it represented as a pure bit string, i.e. as if the arch were big endian? Or is it represented as a mapping onto the bytes of the underlying long?

Bitmaps are represented in Linux in such manners as befit wrong (little) endian machines. I suggest shifting in the opposite direction.

-- wli

#12 lore raw
In reply to Keith Owens
Quoted 2 lines · Paul Jackson
Quoted 2 lines

I still don't know how I will fix the CPU_MASK_ALL static initializor in the multi-word case - since I can't put runtime code in it.

Quoted 1 line · Keith Owens

#define NR_CPUS_WORDS ((NR_CPUS+BITS_PER_LONG-1)/BITS_PER_LONG)

This looks suspiciously like BITS_TO_LONGS(NR_CPUS) =)

Quoted 6 lines · Keith Owens

#define NR_CPUS_UNDEF (NR_CPUS_WORDS*BITS_PER_LONG-NR_CPUS)
#if NR_CPUS_UNDEF == 0
#define CPU_MASK_ALL { [0 ... NR_CPUS_WORDS-1] = ~0UL }
#else
#define CPU_MASK_ALL { [0 ... NR_CPUS_WORDS-2] = ~0UL, ~0UL << NR_CPUS_UNDEF } #endif

Hmm, shouldn't that last one be ~0UL >> NR_CPUS_UNDEF?

-- wli