fix zonelist ordering for NUMA
Subsystems (2)
Review
Quoted 6 lines · On Tue, 2004-02-24 at 01:20, [email protected] wrote:
(quoted diff) +2
-4- for (node = local_node + 1; node < numnodes; node++) - j = build_zonelists_node(NODE_DATA(node), zonelist, j, k); - for (node = 0; node < local_node; node++) - j = build_zonelists_node(NODE_DATA(node), zonelist, j, k); + for (node = 1; node < numnodes; node++) + j = build_zonelists_node(SORTED_NODE_DATA(local_node, node), zonelist, j, k);
Shouldn't that for loop be:
for (node = 0; node < numnodes; node++) j = ....
or we'll be leaving a node out of the zonelists, right?
-Matt
Hi,
Quoted 8 lines
Review
Quoted 2 lines
(quoted diff) +2
-0+ for (node = 1; node < numnodes; node++) + j = build_zonelists_node(SORTED_NODE_DATA(local_node, node), zonelist, j, k);Shouldn't that for loop be:
for (node = 0; node < numnodes; node++) j = ....or we'll be leaving a node out of the zonelists, right?
No. The zonelist for the local_node is built before the code above.
The whole code looks like:
Quoted 6 lines
local_node=pgdat->node_id;
...
j =build_zonelists_node(pgdat, zonelist, j, k);
...
for (node = 1; node < numnodes; node++)j = build_zonelists_node(SORTED_NODE_DATA(local_node,node), zonelist, j, k);
Actually, we might be able to clean it up like:
Quoted 2 lines
for (idx = 0; idx < numnodes; idx++)
j = build_zonelists_node(SORTED_NODE_DATA(local_node,idx), zonelist, j, k);
Best regards.
--
NOMURA, Jun'ichi <[email protected]>
I cleaned up the patch based on the comments from Jesse and Matthew.
Quoted 3 lines
1) make it arch independent
this means having arch code populate a SLIT-like table for use by the generic zonelist building code
I moved the whole function to mm/page_alloc.c.
Quoted 3 lines
3) some systems have pgdats w/o any CPUs associated with them, they need to be dealt with differently than regular nodes, maybe as extensions to an existing node
Headless node is prefered over the nodes with same distance.
Quoted 1 line
2) handle the cases that Erich talked about a bit better
Any idea for doing it in generic way?
Best regards.
--
NOMURA, Jun'ichi <[email protected]>
mm/page_alloc.c +57 -13
@@ -1074,9 +1074,63 @@ static int __init build_zonelists_node(preturn j; } +/** +* find_next_best_node - find the next node that should appear in a given +* node's fallback list +* @node: node whose fallback list we're appending +* @used_node_mask: pointer to the bitmap of already used nodes +* +* We use a number of factors to determine which is the next node that should +* appear on a given node's fallback list. The node should not have appeared +* already in @node's fallback list, and it should be the next closest node +* according to the distance array (which contains arbitrary distance values +* from each node to each node in the system), and should also prefer nodes +* with no CPUs, since presumably they'll have very little allocation pressure +* on them otherwise. +* It returns -1 if no node is found. +*/ +#ifndef node_distance +#define node_distance (from,to) (1) +#endif +#define PENALTY_FOR_NODE_WITH_CPUS (1) + +static int __init find_next_best_node (int node,void *used_node_mask) +{ +int i, n, val; +int min_val =INT_MAX ; +int best_node =-1 ; + +for (i =0 ; i < numnodes; i++) { +/* Start from local node */ + n = (node+i)%numnodes; + +/* Don't want a node to appear more than once */ +if (test_bit (n, used_node_mask)) +continue ; + +/* Use the distance array to find the distance */ + val =node_distance (node, n); + +/* Give preference to headless and unused nodes */ +if (node_to_cpumask (n)) + val +=PENALTY_FOR_NODE_WITH_CPUS ; + +if (val < min_val) { + min_val = val; + best_node = n; + } + } + +if (best_node >=0 ) +set_bit (best_node, used_node_mask); + +return best_node; +} +static void __init build_zonelists (pg_data_t *pgdat) {int i, j, k, node, local_node; +DECLARE_BITMAP (used_mask,MAX_NUMNODES ); local_node = pgdat->node_id;for (i =0 ; i <MAX_NR_ZONES ; i++) {
@@ -1092,19 +1146,9 @@ static void __init build_zonelists(pg_daif (i & __GFP_DMA) k =ZONE_DMA ; - j =build_zonelists_node (pgdat, zonelist, j, k); -/* -* Now we build the zonelist so that it contains the zones -* of all the other nodes. -* We don't want to pressure a particular node, so when -* building the zones for node N, we make sure that the -* zones coming right after the local ones are those from -* node N+1 (modulo N) -*/ -for (node = local_node +1 ; node < numnodes; node++) - j =build_zonelists_node (NODE_DATA (node), zonelist, j, k); -for (node =0 ; node < local_node; node++) - j =build_zonelists_node (NODE_DATA (node), zonelist, j, k); +CLEAR_BITMAP (used_mask,MAX_NUMNODES ); +while ((node =find_next_best_node (local_node, used_mask)) >=0 ) + j =build_zonelists_node (NODE_DATA (node), zonelist, j, k); zonelist->zones[j++] =NULL ; }
Review
Quoted 3 lines · On Wed, Feb 25, 2004 at 07:59:33PM +0900, [email protected] wrote:
(quoted diff) +3
-0+#ifndef node_distance +#define node_distance(from,to) (1) +#endif
please move this to toplogy.h - it'll be usefull in a few other places.
Quoted 1 line
+#define
PENALTY_FOR_NODE_WITH_CPUS(1)
should probably also go to topology.h to allow architectures to change it.
Review
Quoted 1 line
(quoted diff) +1
-0+ for(i = 0; i < numnodes; i++) {
minor nitpick: please leave a space between the for and the opening brace
Review
Quoted 1 line
(quoted diff) +1
-0+ while((node = find_next_best_node(local_node, used_mask)) >= 0)
same here.
Quoted 7 lines · On Wed, Feb 25, 2004 at 07:59:33PM +0900, [email protected] wrote:
I cleaned up the patch based on the comments from Jesse and Matthew.
Quoted 3 lines
1) make it arch independent
this means having arch code populate a SLIT-like table for use by the generic zonelist building codeI moved the whole function to
mm/page_alloc.c.
Looks even better, that was fast! :)
Quoted 5 lines
Quoted 3 lines
3) some systems have pgdats w/o any CPUs associated with them, they need to be dealt with differently than regular nodes, maybe as extensions to an existing node
Headless node is prefered over the nodes with same distance.
I'd be curious to hear about others with similar configurations. On sn2, we may have multiple headless nodes for each node with CPUs. In such a configuration, it seems best to have each node with CPUs 'own' a set of headless nodes, and allocate from them even if they're further away than other nodes with CPUs. I don't think we have to worry about that too much now though, since the algorithm below could be tweaked to do just that easier than the simple sort code I did awhile back.
Quoted 3 lines
Quoted 1 line
2) handle the cases that Erich talked about a bit better
Any idea for doing it in generic way?
We could adjust 'val' below based on an array that weights each node as it's added to a zonelist. I think that would be up to the caller of find_next_best_node() to adjust, but would be used in the routine below. Doing it that way would allow the balancing that Erich was talking about as well as the headless node stuff we want for sn2.
Thanks,
Jesse
Hi,
Quoted 9 lines
Quoted 3 lines
Quoted 1 line
2) handle the cases that Erich talked about a bit better
Any idea for doing it in generic way?
We could adjust 'val' below based on an array that weights each node as it's added to a zonelist. I think that would be up to the caller of
find_next_best_node()to adjust, but would be used in the routine below. Doing it that way would allow the balancing that Erich was talking about as well as the headless node stuff we want for sn2.
Needs consideration for this.
I think the find_next_best_node-loop must be outer to for-each-zonelist loop to do this kind of weighing.
Best regards.
--
NOMURA, Jun'ichi <[email protected]>
I updated the patch.
This version of build_zonelists() is NUMA-specific one. It will handle the situation Erich pointed out better.
For example, when the node_distance(i,j) looks like below:
10 15 15 15 20 20 20 20
15 10 15 15 20 20 20 20
15 15 10 15 20 20 20 20
15 15 15 10 20 20 20 20
20 20 20 20 10 15 15 15
20 20 20 20 15 10 15 15
20 20 20 20 15 15 10 15
20 20 20 20 15 15 15 10
The previous patch generates zonelist in the following order:
Node#00 0 1 2 3 4 5 6 7 Node#01 1 2 3 0 4 5 6 7 Node#02 2 3 0 1 4 5 6 7 Node#03 3 0 1 2 4 5 6 7 Node#04 4 5 6 7 0 1 2 3 Node#05 5 6 7 4 0 1 2 3 Node#06 6 7 4 5 0 1 2 3 Node#07 7 4 5 6 0 1 2 3
With this patch, the order looks like:
Node#00 0 1 2 3 4 5 6 7 Node#01 1 2 3 0 5 6 7 4 Node#02 2 3 0 1 6 7 4 5 Node#03 3 0 1 2 7 4 5 6 Node#04 4 5 6 7 0 1 2 3 Node#05 5 6 7 4 1 2 3 0 Node#06 6 7 4 5 2 3 0 1 Node#07 7 4 5 6 3 0 1 2
Best regards.
--
NOMURA, Jun'ichi <[email protected]>
mm/page_alloc.c +108 -1
@@ -1074,6 +1074,106 @@ static int __init build_zonelists_node(preturn j; } +#ifdef CONFIG_NUMA +#define MAX_NODE_LOAD (numnodes) +static int __initdata node_load[MAX_NUMNODES ]; +/** +* find_next_best_node - find the next node that should appear in a given +* node's fallback list +* @node: node whose fallback list we're appending +* @used_node_mask: pointer to the bitmap of already used nodes +* +* We use a number of factors to determine which is the next node that should +* appear on a given node's fallback list. The node should not have appeared +* already in @node's fallback list, and it should be the next closest node +* according to the distance array (which contains arbitrary distance values +* from each node to each node in the system), and should also prefer nodes +* with no CPUs, since presumably they'll have very little allocation pressure +* on them otherwise. +* It returns -1 if no node is found. +*/ +static int __init find_next_best_node (int node,void *used_node_mask) +{ +int i, n, val; +int min_val =INT_MAX ; +int best_node =-1 ; + +for (i =0 ; i < numnodes; i++) { +/* Start from local node */ + n = (node+i)%numnodes; + +/* Don't want a node to appear more than once */ +if (test_bit (n, used_node_mask)) +continue ; + +/* Use the distance array to find the distance */ + val =node_distance (node, n); + +/* Give preference to headless and unused nodes */ +if (node_to_cpumask (n)) + val +=PENALTY_FOR_NODE_WITH_CPUS ; + +/* Slight preference for less loaded node */ + val *= (MAX_NODE_LOAD *MAX_NUMNODES ); + val += node_load[n]; + +if (val < min_val) { + min_val = val; + best_node = n; + } + } + +if (best_node >=0 ) +set_bit (best_node, used_node_mask); + +return best_node; +} + +static void __init build_zonelists (pg_data_t *pgdat) +{ +int i, j, k, node, local_node; +int prev_node, load; +struct zonelist *zonelist; +DECLARE_BITMAP (used_mask,MAX_NUMNODES ); + +/* initialize zonelists */ +for (i =0 ; i <MAX_NR_ZONES ; i++) { + zonelist = pgdat->node_zonelists + i; +memset (zonelist,0 ,sizeof (*zonelist)); + zonelist->zones[0 ] =NULL ; + } + +/* NUMA-aware ordering of nodes */ + local_node = pgdat->node_id; + load = numnodes; + prev_node = local_node; +CLEAR_BITMAP (used_mask,MAX_NUMNODES ); +while ((node =find_next_best_node (local_node, used_mask)) >=0 ) { +/* +* We don't want to pressure a particular node. +* So adding penalty to the first node in same +* distance group to make it round-robin. +*/ +if (node_distance (local_node, node) !=node_distance (local_node, prev_node)) + node_load[node] += load; + prev_node = node; + load--; +for (i =0 ; i <MAX_NR_ZONES ; i++) { + zonelist = pgdat->node_zonelists + i; +for (j =0 ; zonelist->zones[j] !=NULL ; j++); + + k =ZONE_NORMAL ; +if (i & __GFP_HIGHMEM) + k =ZONE_HIGHMEM ; +if (i & __GFP_DMA) + k =ZONE_DMA ; + + j =build_zonelists_node (NODE_DATA (node), zonelist, j, k); + zonelist->zones[j] =NULL ; + } + } +} +#else static void __init build_zonelists (pg_data_t *pgdat) {int i, j, k, node, local_node;
@@ -1109,7 +1209,8 @@ static void __init build_zonelists(pg_da zonelist->zones[j++] = NULL; } } +#endif void __init build_all_zonelists (void ) { --- linux/include/asm-generic/topology.h 2004/02/18 07:21:59 1.1.1.5 +++ linux/include/asm-generic/topology.h 2004/02/27 10:55:52
@@ -44,6 +44,12 @@#ifndef pcibus_to_cpumask#define pcibus_to_cpumask (bus) (cpu_online_map)#endif +#ifndef node_distance +#define node_distance (from,to) (from != to) +#endif +#ifndef PENALTY_FOR_NODE_WITH_CPUS +#define PENALTY_FOR_NODE_WITH_CPUS (1) +#endif /* Cross-node load balancing interval. */ #ifndef NODE_BALANCE_RATE
Index: linux/include/asm-i386/topology.h
===================================================================
RCS file: /home/cvsadm/cvsroot/linux2.5/linux/include/asm-i386/topology.h,v retrieving revision 1.1.1.6
include/asm-i386/topology.h +6 -0
@@ -66,6 +66,12 @@ static inline cpumask_t pcibus_to_cpumasreturn node_to_cpumask (mp_bus_id_to_node[bus]); } +/* Node-to-Node distance */ +static inline int node_distance (int from,int to) +{ +return (from != to); +} +/* Cross-node load balancing interval. */ #define NODE_BALANCE_RATE 100
Quoted 3 lines · On Fri, Feb 27, 2004 at 09:19:58PM +0900, [email protected] wrote:
I updated the patch.
This version ofbuild_zonelists()is NUMA-specific one. It will handle the situation Erich pointed out better.
This patch looks great to me. Care to send it on to Andrew for inclusion into his tree?
Thanks,
Jesse
Quoted 6 lines
Quoted 3 lines
I updated the patch.
This version ofbuild_zonelists()is NUMA-specific one. It will handle the situation Erich pointed out better.This patch looks great to me. Care to send it on to Andrew for inclusion into his tree?
Thank you. I'll send it to Andrew.
Best regards.
--
NOMURA, Jun'ichi <[email protected]>