__alloc_pages - NUMA and lower zone protection

PATCH In review Martin Hicks 3 participants 5 messages Feb 13, 2004 – Feb 18, 2004

Subsystems (4)

Memory management MM core Page allocator MGLRU

lore

Share & tools

lore

Martin Hicks

author

2004-02-13 18:37 UTC #0 lore raw

PATCH 1/1 __alloc_pages - NUMA and lower zone protection

Hi,

There is a problem with the current __alloc pages on a machine with many nodes. As we go down the zones[] list, we may move onto other nodes. Each time we go to the next zone we protect these zones by doing "min += local_low".

This is quite appropriate on a machine with one node, but wrong on machines with other nodes. To illustrate, here is an example. On a 256 node Altix machine, a request on node 0 for 2MB requires just over 600MB of free memory on the 256th node in order to fullfil the "min" requirements if all other nodes are low on memory. This could leave 73GB of memory unallocated across all nodes.

This patch keeps the same semantics for lower_zone_protection, but only provides protection for higher priority zones in the same node.

The patch seems to do the right thing on my non-NUMA zx1 ia64 machine (which has ZONE_DMA and ZONE_NORMAL) as well as the multi-node Altix.

thanks
mh

Signature · 2 lines

Martin Hicks                Wild Open Source Inc.
[email protected]     613-266-2296

===== include/linux/mmzone.h 1.51 vs edited =====

include/linux/mmzone.h +1 -0

@@ -70,6 +70,7 @@
 	spinlock_t		lock;
 	unsigned long		free_pages;
 	unsigned long		pages_min, pages_low, pages_high;
+	unsigned long		zone_type;
 
 	ZONE_PADDING(_pad1_)

===== mm/page_alloc.c 1.184 vs edited =====

mm/page_alloc.c +17 ~~-16~~

@@ -41,6 +41,7 @@
 int nr_swap_pages;
 int numnodes = 1;
 int sysctl_lower_zone_protection = 0;
+static int max_zone;	/* Highest zone number that contains pages */
 
 EXPORT_SYMBOL(totalram_pages);
 EXPORT_SYMBOL(nr_swap_pages);

@@ -557,27 +558,24 @@
 		return NULL;
 
 	/* Go through the zonelist once, looking for a zone with enough free */
-	min = 1UL << order;
 	for (i = 0; zones[i] != NULL; i++) {
 		struct zone *z = zones[i];
-		unsigned long local_low;
+		unsigned long local_low = z->pages_low;
 
 		/*
 		 * This is the fabled 'incremental min'. We let real-time tasks
 		 * dip their real-time paws a little deeper into reserves.
 		 */
-		local_low = z->pages_low;
 		if (rt_task(p))
 			local_low >>= 1;
-		min += local_low;
-
+		min = (1UL << order) + local_low;
+		min += local_low * sysctl_lower_zone_protection * (max_zone - z->zone_type);
 		if (z->free_pages >= min ||
 				(!wait && z->free_pages >= z->pages_high)) {
 			page = buffered_rmqueue(z, order, cold);
 			if (page)
-		       		goto got_pg;
+				goto got_pg;
 		}
-		min += z->pages_low * sysctl_lower_zone_protection;
 	}
 
 	/* we're somewhat low on memory, failed to find what we needed */

@@ -585,24 +583,23 @@
 		wakeup_kswapd(zones[i]);
 
 	/* Go through the zonelist again, taking __GFP_HIGH into account */
-	min = 1UL << order;
 	for (i = 0; zones[i] != NULL; i++) {
-		unsigned long local_min;
 		struct zone *z = zones[i];
+		unsigned long local_min = z->pages_min;
 
-		local_min = z->pages_min;
 		if (gfp_mask & __GFP_HIGH)
 			local_min >>= 2;
 		if (rt_task(p))
 			local_min >>= 1;
-		min += local_min;
+		min = (1UL << order) + local_min;
+		min += local_min * sysctl_lower_zone_protection * (max_zone - z->zone_type);
+
 		if (z->free_pages >= min ||
 				(!wait && z->free_pages >= z->pages_high)) {
 			page = buffered_rmqueue(z, order, cold);
 			if (page)
 				goto got_pg;
 		}
-		min += local_min * sysctl_lower_zone_protection;
 	}
 
 	/* here we're in the low on memory slow path */

@@ -634,18 +631,17 @@
 	p->flags &= ~PF_MEMALLOC;
 
 	/* go through the zonelist yet one more time */
-	min = 1UL << order;
 	for (i = 0; zones[i] != NULL; i++) {
 		struct zone *z = zones[i];
 
-		min += z->pages_min;
+		min = (1UL << order) + z->pages_min;
+		min += z->pages_min * sysctl_lower_zone_protection * (max_zone - z->zone_type);
 		if (z->free_pages >= min ||
 				(!wait && z->free_pages >= z->pages_high)) {
 			page = buffered_rmqueue(z, order, cold);
 			if (page)
 				goto got_pg;
 		}
-		min += z->pages_low * sysctl_lower_zone_protection;
 	}
 
 	/*

@@ -1107,7 +1103,11 @@
  			j = build_zonelists_node(NODE_DATA(node), zonelist, j, k);
  
 		zonelist->zones[j++] = NULL;
-	} 
+
+		if (pgdat->node_zones[i].present_pages > 0)
+			if (i > max_zone)
+				max_zone = i;
+       }
 }
 
 void __init build_all_zonelists(void)

@@ -1246,6 +1246,7 @@
 		spin_lock_init(&zone->lru_lock);
 		zone->zone_pgdat = pgdat;
 		zone->free_pages = 0;
+		zone->zone_type = j;
 
 		zone->temp_priority = zone->prev_priority = DEF_PRIORITY;

Nick Piggin

2004-02-14 00:01 UTC #1 lore raw

Quoted 14 lines · Martin Hicks

Hi,
There is a problem with the current __alloc pages on a machine with many nodes. As we go down the zones[] list, we may move onto other nodes. Each time we go to the next zone we protect these zones by doing "min += local_low".
This is quite appropriate on a machine with one node, but wrong on machines with other nodes. To illustrate, here is an example. On a 256 node Altix machine, a request on node 0 for 2MB requires just over 600MB of free memory on the 256th node in order to fullfil the "min" requirements if all other nodes are low on memory. This could leave 73GB of memory unallocated across all nodes.

Quoted 7 lines

This patch keeps the same semantics for lower_zone_protection, but only provides protection for higher priority zones in the same node.
The patch seems to do the right thing on my non-NUMA zx1 ia64 machine (which has ZONE_DMA and ZONE_NORMAL) as well as the multi-node Altix.

Could you add a comment or two, please?

Martin Hicks

author

2004-02-14 02:18 UTC #2 lore raw

Quoted 10 lines · Nick Piggin

Quoted 5 lines · Martin Hicks
The patch seems to do the right thing on my non-NUMA zx1 ia64 machine (which has ZONE_DMA and ZONE_NORMAL) as well as the multi-node Altix.
Could you add a comment or two, please?

Okay. Same patch, with a comment.

Signature · 2 lines

Martin Hicks                Wild Open Source Inc.
[email protected]     613-266-2296

# This is a BitKeeper generated patch for the following project:
# Project Name: Linux kernel tree
# This patch format is intended for GNU patch command version 2.5 or higher. # This patch includes the following deltas:
# ChangeSet 1.1631 -> 1.1632
# mm/page_alloc.c 1.185 -> 1.186
# include/linux/mmzone.h 1.52 -> 1.53
#
# The following is the BitKeeper ChangeSet Log
# --------------------------------------------
# 04/02/13 [email protected] 1.1632
# Change incremental min in __alloc_pages to ensure that min
# doesn't increase across nodes.
# --------------------------------------------
#

include/linux/mmzone.h +1 -0

diff -Nru a/include/linux/mmzone.h b/include/linux/mmzone.h
@@ -70,6 +70,7 @@
 	spinlock_t		lock;
 	unsigned long		free_pages;
 	unsigned long		pages_min, pages_low, pages_high;
+	unsigned long		zone_type;
 
 	ZONE_PADDING(_pad1_)

mm/page_alloc.c +23 ~~-16~~

diff -Nru a/mm/page_alloc.c b/mm/page_alloc.c
@@ -41,6 +41,7 @@
 int nr_swap_pages;
 int numnodes = 1;
 int sysctl_lower_zone_protection = 0;
+static int max_zone;	/* Highest zone number that contains pages */
 
 EXPORT_SYMBOL(totalram_pages);
 EXPORT_SYMBOL(nr_swap_pages);

@@ -559,27 +560,26 @@
 		return NULL;
 
 	/* Go through the zonelist once, looking for a zone with enough free */
-	min = 1UL << order;
 	for (i = 0; zones[i] != NULL; i++) {
 		struct zone *z = zones[i];
-		unsigned long local_low;
+		unsigned long local_low = z->pages_low;
 
 		/*
 		 * This is the fabled 'incremental min'. We let real-time tasks
 		 * dip their real-time paws a little deeper into reserves.
 		 */
-		local_low = z->pages_low;
 		if (rt_task(p))
 			local_low >>= 1;
-		min += local_low;
-
+		/* Reset min on each iteration so we don't accumulate
+		 * the min across multiple nodes */
+		min = (1UL << order) + local_low;
+		min += local_low * sysctl_lower_zone_protection * (max_zone - z->zone_type);
 		if (z->free_pages >= min ||
 				(!wait && z->free_pages >= z->pages_high)) {
 			page = buffered_rmqueue(z, order, cold);
 			if (page)
-		       		goto got_pg;
+				goto got_pg;
 		}
-		min += z->pages_low * sysctl_lower_zone_protection;
 	}
 
 	/* we're somewhat low on memory, failed to find what we needed */

@@ -587,24 +587,25 @@
 		wakeup_kswapd(zones[i]);
 
 	/* Go through the zonelist again, taking __GFP_HIGH into account */
-	min = 1UL << order;
 	for (i = 0; zones[i] != NULL; i++) {
-		unsigned long local_min;
 		struct zone *z = zones[i];
+		unsigned long local_min = z->pages_min;
 
-		local_min = z->pages_min;
 		if (gfp_mask & __GFP_HIGH)
 			local_min >>= 2;
 		if (rt_task(p))
 			local_min >>= 1;
-		min += local_min;
+		/* Reset min on each iteration so we don't accumulate
+		 * the min across multiple nodes */
+		min = (1UL << order) + local_min;
+		min += local_min * sysctl_lower_zone_protection * (max_zone - z->zone_type);
+
 		if (z->free_pages >= min ||
 				(!wait && z->free_pages >= z->pages_high)) {
 			page = buffered_rmqueue(z, order, cold);
 			if (page)
 				goto got_pg;
 		}
-		min += local_min * sysctl_lower_zone_protection;
 	}
 
 	/* here we're in the low on memory slow path */

@@ -636,18 +637,19 @@
 	p->flags &= ~PF_MEMALLOC;
 
 	/* go through the zonelist yet one more time */
-	min = 1UL << order;
 	for (i = 0; zones[i] != NULL; i++) {
 		struct zone *z = zones[i];
 
-		min += z->pages_min;
+		/* Reset min on each iteration so we don't accumulate
+		 * the min across multiple nodes */
+		min = (1UL << order) + z->pages_min;
+		min += z->pages_min * sysctl_lower_zone_protection * (max_zone - z->zone_type);
 		if (z->free_pages >= min ||
 				(!wait && z->free_pages >= z->pages_high)) {
 			page = buffered_rmqueue(z, order, cold);
 			if (page)
 				goto got_pg;
 		}
-		min += z->pages_low * sysctl_lower_zone_protection;
 	}
 
 	/*

@@ -1115,7 +1117,11 @@
  			j = build_zonelists_node(NODE_DATA(node), zonelist, j, k);
  
 		zonelist->zones[j++] = NULL;
-	} 
+
+		if (pgdat->node_zones[i].present_pages > 0)
+			if (i > max_zone)
+				max_zone = i;
+       }
 }
 
 void __init build_all_zonelists(void)

@@ -1258,6 +1264,7 @@
 		spin_lock_init(&zone->lru_lock);
 		zone->zone_pgdat = pgdat;
 		zone->free_pages = 0;
+		zone->zone_type = j;
 
 		zone->temp_priority = zone->prev_priority = DEF_PRIORITY;

Andrew Morton

2004-02-17 23:00 UTC #3 lore raw

In reply to Martin Hicks

Quoted 16 lines · Martin Hicks

Hi,
There is a problem with the current __alloc pages on a machine with many nodes. As we go down the zones[] list, we may move onto other nodes. Each time we go to the next zone we protect these zones by doing "min += local_low".
This is quite appropriate on a machine with one node, but wrong on machines with other nodes. To illustrate, here is an example. On a 256 node Altix machine, a request on node 0 for 2MB requires just over 600MB of free memory on the 256th node in order to fullfil the "min" requirements if all other nodes are low on memory. This could leave 73GB of memory unallocated across all nodes.

Quoted 6 lines

This patch keeps the same semantics for lower_zone_protection, but only provides protection for higher priority zones in the same node.
The patch seems to do the right thing on my non-NUMA zx1 ia64 machine (which has ZONE_DMA and ZONE_NORMAL) as well as the multi-node Altix.

I appreciate the problem. We do need to fix this.

include/linux/mmzone.h line 73

Quoted 8 lines

===== include/linux/mmzone.h 1.51 vs edited =====

include/linux/mmzone.h +1 -0

@@ -70,6 +70,7 @@
 	spinlock_t		lock;
 	unsigned long		free_pages;
 	unsigned long		pages_min, pages_low, pages_high;
+	unsigned long		zone_type;

This should be called `zone_index' or something, yes? What, semantically, is it supposed to mean?

Quoted 30 lines

mm/page_alloc.c +3 -5

@@ -41,6 +41,7 @@
 int nr_swap_pages;
 int numnodes = 1;
 int sysctl_lower_zone_protection = 0;
+static int max_zone;	/* Highest zone number that contains pages */
 
 EXPORT_SYMBOL(totalram_pages);
 EXPORT_SYMBOL(nr_swap_pages);

@@ -557,27 +558,24 @@
 		return NULL;
 
 	/* Go through the zonelist once, looking for a zone with enough free */
-	min = 1UL << order;
 	for (i = 0; zones[i] != NULL; i++) {
 		struct zone *z = zones[i];
-		unsigned long local_low;
+		unsigned long local_low = z->pages_low;
 
 		/*
 		 * This is the fabled 'incremental min'. We let real-time tasks
 		 * dip their real-time paws a little deeper into reserves.
 		 */
-		local_low = z->pages_low;
 		if (rt_task(p))
 			local_low >>= 1;
-		min += local_low;
-
+		min = (1UL << order) + local_low;

mm/page_alloc.c line 579

Quoted 10 lines

mm/page_alloc.c +2 -2

+		min += local_low * sysctl_lower_zone_protection * (max_zone - z->zone_type);
 		if (z->free_pages >= min ||
 				(!wait && z->free_pages >= z->pages_high)) {
 			page = buffered_rmqueue(z, order, cold);
 			if (page)
-		       		goto got_pg;
+				goto got_pg;
 		}
-		min += z->pages_low * sysctl_lower_zone_protection;
 	}

This does represent an algorithmic change to the zone fallback code. Previously we were using the pages_low value of the higher zones and were feeding that forward into decisions about the availablility of pages in the lower zones.

You've changed this so that each zone is considered independently of the others, and its offset into the zone list is used in some manner to set the decision threshold. That could work OK; I'd need to go into a deep trance to remember why we did it the current way.

What you've done here is to make the `zone_type' number represent the index of the zone *within its node*, yes? So for the "highest" zone within a node, (max_zone - z->zone_type) is zero, then it is "1", then it is "2", as we walk the zonelist, yes?

Why is it safe to assume that all nodes have the same number of zones (via
max_zone)? Perhaps this should be a pgdat member.

Apart from the rt_task thing, the code as you have it here can all be removed from the fastpath: the thresholds can all be precalculated within the sysctl handler (both lower_zone_protection and min_free_kbytes) and the only thing which we need to do in the allocator is to handle RT tasks. This would involve moving the lower_zone_protection calculation into setup_per_zone_pages_min(). In fact this is a change which we should make regardless of your patch.

This is a significant change you've made here and I'd like to hear (a lot) more about the thinking, testing and measurement which went into it please.

Martin Hicks

author

2004-02-18 16:19 UTC #4 lore raw

Quoted 13 lines · Andrew Morton

include/linux/mmzone.h line 73
Quoted 8 lines · Martin Hicks
===== include/linux/mmzone.h 1.51 vs edited =====
include/linux/mmzone.h +1 -0
@@ -70,6 +70,7 @@
 	spinlock_t		lock;
 	unsigned long		free_pages;
 	unsigned long		pages_min, pages_low, pages_high;
+	unsigned long		zone_type;
This should be called `zone_index' or something, yes? What, semantically, is it supposed to mean?

It's the highest zone number that contains pages. i.e., on Altix it is 0 (only ZONE_DMA), on an x86 machine with highmem present it is 2 (has pages in ZONE_HIGHMEM).

Quoted 46 lines

Quoted 30 lines

mm/page_alloc.c +3 -5

@@ -41,6 +41,7 @@
 int nr_swap_pages;
 int numnodes = 1;
 int sysctl_lower_zone_protection = 0;
+static int max_zone;	/* Highest zone number that contains pages */
 
 EXPORT_SYMBOL(totalram_pages);
 EXPORT_SYMBOL(nr_swap_pages);

@@ -557,27 +558,24 @@
 		return NULL;
 
 	/* Go through the zonelist once, looking for a zone with enough free */
-	min = 1UL << order;
 	for (i = 0; zones[i] != NULL; i++) {
 		struct zone *z = zones[i];
-		unsigned long local_low;
+		unsigned long local_low = z->pages_low;
 
 		/*
 		 * This is the fabled 'incremental min'. We let real-time tasks
 		 * dip their real-time paws a little deeper into reserves.
 		 */
-		local_low = z->pages_low;
 		if (rt_task(p))
 			local_low >>= 1;
-		min += local_low;
-
+		min = (1UL << order) + local_low;

mm/page_alloc.c line 579

Quoted 10 lines

mm/page_alloc.c +2 -2

+		min += local_low * sysctl_lower_zone_protection * (max_zone - z->zone_type);
 		if (z->free_pages >= min ||
 				(!wait && z->free_pages >= z->pages_high)) {
 			page = buffered_rmqueue(z, order, cold);
 			if (page)
-		       		goto got_pg;
+				goto got_pg;
 		}
-		min += z->pages_low * sysctl_lower_zone_protection;
 	}

Quoted 4 lines

You've changed this so that each zone is considered independently of the others, and its offset into the zone list is used in some manner to set the decision threshold. That could work OK; I'd need to go into a deep trance to remember why we did it the current way.

Yes. I realized this after I sent the patch. Apparently I wasn't in enough of a VM trance when I wrote the e-mail.

Quoted 5 lines

What you've done here is to make the `zone_type' number represent the index of the zone *within its node*, yes? So for the "highest" zone within a node, (max_zone - z->zone_type) is zero, then it is "1", then it is "2", as we walk the zonelist, yes?

Correct.

Quoted 2 lines

Why is it safe to assume that all nodes have the same number of zones (via
max_zone)? Perhaps this should be a pgdat member.

Perhaps not, but I think the only penalty is to over guess "min" by a small factor. Would accessing some field of pgdat on each iteration not lead to a lot of dirty cachelines as we move through many nodes?

Quoted 7 lines

Apart from the rt_task thing, the code as you have it here can all be removed from the fastpath: the thresholds can all be precalculated within the sysctl handler (both lower_zone_protection and min_free_kbytes) and the only thing which we need to do in the allocator is to handle RT tasks. This would involve moving the lower_zone_protection calculation into setup_per_zone_pages_min(). In fact this is a change which we should make regardless of your patch.

Agreed.

Quoted 2 lines

This is a significant change you've made here and I'd like to hear (a lot) more about the thinking, testing and measurement which went into it please.

I've done some preliminary testing with the patch above. I'll do some more work on what you've asked for above and get some better numbers.

thanks for your input,
mh

Signature · 2 lines

Martin Hicks                Wild Open Source Inc.
[email protected]     613-266-2296