Skip to contentSkip to conversation

improve speed of freeing bootmem

PATCH In review Josh Aas 3 participants 4 messages Aug 6, 2004

Subsystems (2)
Memory management MM core
lore
Share & tools
lore

Josh Aas

author
#0 lore raw

PATCH 1/1 improve speed of freeing bootmem

Attached is a patch that greatly improves the speed of freeing boot memory. On ia64 machines with 2GB or more memory (I didn't test with less, but I can't imagine there being a problem), the speed improvement is about 75% for the function free_all_bootmem_core. This translates to savings on the order of 1 minute / TB of memory during boot time. That number comes from testing on a machine with 512GB, and extrapolating based on profiling of an unpatched 4TB machine. For 4 and 8 TB machines, the time spent in this function is about 1 minutes/TB, which is painful especially given that there is no indication of what is going on put to the console (this issue to possibly be addressed later).

The basic idea is to free higher order pages instead of going through every single one. Also, some unnecessary atomic operations are done away with and replaced with non-atomic equivalents, and prefetching is done where it helps the most. For a more in-depth discusion of this patch, please see the linux-ia64 archives (topic is "free bootmem feedback patch").

The patch is originally Tony Luck's, and I added some further optimizations (non-atomic ops improvements and prefetching).

Signed-off-by Tony Luck <[email protected]>
Signed-off-by Josh Aas <[email protected]>
Signature · 4 lines
Josh Aas
Silicon Graphics, Inc. (SGI)
Linux System Software
651-683-3068
mm/bootmem.c +22 -3
@@ -259,6 +259,7 @@ static unsigned long __init free_all_boo
 	unsigned long i, count, total = 0;
 	unsigned long idx;
 	unsigned long *map; 
+	int gofast = 0;
 
 	BUG_ON(!bdata->node_bootmem_map);
 

@@ -267,14 +268,32 @@ static unsigned long __init free_all_boo
 	page = virt_to_page(phys_to_virt(bdata->node_boot_start));
 	idx = bdata->node_low_pfn - (bdata->node_boot_start >> PAGE_SHIFT);
 	map = bdata->node_bootmem_map;
+	if (bdata->node_boot_start == 0 ||
+	    ffs(bdata->node_boot_start) - PAGE_SHIFT > ffs(BITS_PER_LONG))
+		gofast = 1;
 	for (i = 0; i < idx; ) {
 		unsigned long v = ~map[i / BITS_PER_LONG];
-		if (v) {
+		if (gofast && v == ~0UL) {
+			int j;
+
+			count += BITS_PER_LONG;
+			ClearPageReservedNoAtomic(page);
+			set_page_count(page, 1);
+			for (j = 1; j < BITS_PER_LONG; j++) {
+				if (j + 16 < BITS_PER_LONG) {
+                      			prefetchw(page + j + 16);
+                                }
+				ClearPageReservedNoAtomic(page + j);
+			}	
+			__free_pages(page, ffs(BITS_PER_LONG)-1);
+			i += BITS_PER_LONG;
+			page += BITS_PER_LONG;
+		} else if (v) {
 			unsigned long m;
 			for (m = 1; m && i < idx; m<<=1, page++, i++) {
 				if (v & m) {
 					count++;
-					ClearPageReserved(page);
+					ClearPageReservedNoAtomic(page);
 					set_page_count(page, 1);
 					__free_page(page);
 				}

@@ -294,7 +313,7 @@ static unsigned long __init free_all_boo
 	count = 0;
 	for (i = 0; i < ((bdata->node_low_pfn-(bdata->node_boot_start >> PAGE_SHIFT))/8 + PAGE_SIZE-1)/PAGE_SIZE; i++,page++) {
 		count++;
-		ClearPageReserved(page);
+		ClearPageReservedNoAtomic(page);
 		set_page_count(page, 1);
 		__free_page(page);
 	}
include/linux/page-flags.h +1 -0
@@ -236,6 +236,7 @@ extern unsigned long __read_page_state(u
 #define PageReserved(page)	test_bit(PG_reserved, &(page)->flags)
 #define SetPageReserved(page)	set_bit(PG_reserved, &(page)->flags)
 #define ClearPageReserved(page)	clear_bit(PG_reserved, &(page)->flags)
+#define ClearPageReservedNoAtomic(page)	(page)->flags &= ~(1UL << PG_reserved)
 
 #define SetPagePrivate(page)	set_bit(PG_private, &(page)->flags)
 #define ClearPagePrivate(page)	clear_bit(PG_private, &(page)->flags)
#1 lore raw
Quoted 3 lines · Josh Aas

Attached is a patch that greatly improves the speed of freeing boot memory.

hm, OK. I have a vague feeling that Bill Irwin had patches to fix this up ages ago.

A few nits:

Quoted 11 lines
mm/bootmem.c +1 -0
@@ -259,6 +259,7 @@ static unsigned long __init free_all_boo
 	unsigned long i, count, total = 0;
 	unsigned long idx;
 	unsigned long *map; 
+	int gofast = 0;
 
 	BUG_ON(!bdata->node_bootmem_map);

mm/bootmem.c static unsigned long __init free_all_boo · line 273

Quoted 6 lines
mm/bootmem.c +3 -0
@@ -267,14 +268,32 @@ static unsigned long __init free_all_boo
 	page = virt_to_page(phys_to_virt(bdata->node_boot_start));
 	idx = bdata->node_low_pfn - (bdata->node_boot_start >> PAGE_SHIFT);
 	map = bdata->node_bootmem_map;
+	if (bdata->node_boot_start = 0 ||
+	    ffs(bdata->node_boot_start) - PAGE_SHIFT > ffs(BITS_PER_LONG))
+		gofast = 1;

A comment describing the above reasoning would be nice.

mm/bootmem.c static unsigned long __init free_all_boo · line 285

Quoted 13 lines
mm/bootmem.c +10 -1
 	for (i = 0; i < idx; ) {
 		unsigned long v = ~map[i / BITS_PER_LONG];
-		if (v) {
+		if (gofast && v = ~0UL) {
+			int j;
+
+			count += BITS_PER_LONG;
+			ClearPageReservedNoAtomic(page);
+			set_page_count(page, 1);
+			for (j = 1; j < BITS_PER_LONG; j++) {
+				if (j + 16 < BITS_PER_LONG) {
+                      			prefetchw(page + j + 16);
+                                }

The whitespace/tabbing has gone funny here.

mm/bootmem.c static unsigned long __init free_all_boo · line 286

Quoted 1 line
mm/bootmem.c +1 -0
+#define ClearPageReservedNoAtomic(page)	(page)->flags &= ~(1UL << PG_reserved)

The naming convention we used in 2.4 for the nonatomic operation was __ClearPageReserved(), so can we please stick with that?

And this macro can use __clear_bit() rather than open-coding it.

#2 lore raw
Quoted 2 lines · Josh Aas
Quoted 2 lines

Attached is a patch that greatly improves the speed of freeing boot memory.

Quoted 2 lines · Andrew Morton

hm, OK. I have a vague feeling that Bill Irwin had patches to fix this up ages ago.

I'm going to do some further work here and bring some patches that are simplifications of the most widely distributed ones I wrote up to current, get them tested on a few architectures, and so on. The testing cycle for this will probably take a couple of weeks, and it's a much larger change, so I think Josh's solution is a good interim solution. Merging it also helps in the event that the data structure changes I'm working on don't work out or end up going through an unusually long testing cycle.

-- wli

author
#3 lore raw
In reply to Andrew Morton

New patch is attached.

Signed-off-by Tony Luck <[email protected]>
Signed-off-by Josh Aas <[email protected]>
Signature · 4 lines
Josh Aas
Silicon Graphics, Inc. (SGI)
Linux System Software
651-683-3068
Quoted 52 lines · Andrew Morton
Quoted 1 line · Josh Aas

Attached is a patch that greatly improves the speed of freeing boot memory.

hm, OK. I have a vague feeling that Bill Irwin had patches to fix this up ages ago.

A few nits:

Quoted 11 lines
mm/bootmem.c +1 -0
@@ -259,6 +259,7 @@ static unsigned long __init free_all_boo
 	unsigned long i, count, total = 0;
 	unsigned long idx;
 	unsigned long *map; 
+	int gofast = 0;
 
 	BUG_ON(!bdata->node_bootmem_map);

mm/bootmem.c static unsigned long __init free_all_boo · line 273

Quoted 6 lines
mm/bootmem.c +3 -0
@@ -267,14 +268,32 @@ static unsigned long __init free_all_boo
 	page = virt_to_page(phys_to_virt(bdata->node_boot_start));
 	idx = bdata->node_low_pfn - (bdata->node_boot_start >> PAGE_SHIFT);
 	map = bdata->node_bootmem_map;
+	if (bdata->node_boot_start == 0 ||
+	    ffs(bdata->node_boot_start) - PAGE_SHIFT > ffs(BITS_PER_LONG))
+		gofast = 1;

A comment describing the above reasoning would be nice.

mm/bootmem.c static unsigned long __init free_all_boo · line 285

Quoted 13 lines
mm/bootmem.c +10 -1
 	for (i = 0; i < idx; ) {
 		unsigned long v = ~map[i / BITS_PER_LONG];
-		if (v) {
+		if (gofast && v == ~0UL) {
+			int j;
+
+			count += BITS_PER_LONG;
+			ClearPageReservedNoAtomic(page);
+			set_page_count(page, 1);
+			for (j = 1; j < BITS_PER_LONG; j++) {
+				if (j + 16 < BITS_PER_LONG) {
+                      			prefetchw(page + j + 16);
+                                }

The whitespace/tabbing has gone funny here.

Quoted 7 lines

mm/bootmem.c static unsigned long __init free_all_boo · line 286

Quoted 1 line
mm/bootmem.c +1 -0
+#define ClearPageReservedNoAtomic(page)	(page)->flags &= ~(1UL << PG_reserved)

The naming convention we used in 2.4 for the nonatomic operation was __ClearPageReserved(), so can we please stick with that?

And this macro can use __clear_bit() rather than open-coding it.

bootmem.c renamed from bootmem.c.orig +23 -3
@@ -259,6 +259,7 @@ static unsigned long __init free_all_boo
 	unsigned long i, count, total = 0;
 	unsigned long idx;
 	unsigned long *map; 
+	int gofast = 0;
 
 	BUG_ON(!bdata->node_bootmem_map);
 

@@ -267,14 +268,33 @@ static unsigned long __init free_all_boo
 	page = virt_to_page(phys_to_virt(bdata->node_boot_start));
 	idx = bdata->node_low_pfn - (bdata->node_boot_start >> PAGE_SHIFT);
 	map = bdata->node_bootmem_map;
+	/* Check physaddr is O(LOG2(BITS_PER_LONG)) page aligned */
+	if (bdata->node_boot_start == 0 ||
+	    ffs(bdata->node_boot_start) - PAGE_SHIFT > ffs(BITS_PER_LONG))
+		gofast = 1;
 	for (i = 0; i < idx; ) {
 		unsigned long v = ~map[i / BITS_PER_LONG];
-		if (v) {
+		if (gofast && v == ~0UL) {
+			int j;
+
+			count += BITS_PER_LONG;
+			__ClearPageReserved(page);
+			set_page_count(page, 1);
+			for (j = 1; j < BITS_PER_LONG; j++) {
+				if (j + 16 < BITS_PER_LONG) {
+					prefetchw(page + j + 16);
+				}
+				__ClearPageReserved(page + j);
+			}
+			__free_pages(page, ffs(BITS_PER_LONG)-1);
+			i += BITS_PER_LONG;
+			page += BITS_PER_LONG;
+		} else if (v) {
 			unsigned long m;
 			for (m = 1; m && i < idx; m<<=1, page++, i++) {
 				if (v & m) {
 					count++;
-					ClearPageReserved(page);
+					__ClearPageReserved(page);
 					set_page_count(page, 1);
 					__free_page(page);
 				}

@@ -294,7 +314,7 @@ static unsigned long __init free_all_boo
 	count = 0;
 	for (i = 0; i < ((bdata->node_low_pfn-(bdata->node_boot_start >> PAGE_SHIFT))/8 + PAGE_SIZE-1)/PAGE_SIZE; i++,page++) {
 		count++;
-		ClearPageReserved(page);
+		__ClearPageReserved(page);
 		set_page_count(page, 1);
 		__free_page(page);
 	}
linux/page-flags.h renamed from linux/page-flags.h.orig +1 -0
@@ -236,6 +236,7 @@ extern unsigned long __read_page_state(u
 #define PageReserved(page)	test_bit(PG_reserved, &(page)->flags)
 #define SetPageReserved(page)	set_bit(PG_reserved, &(page)->flags)
 #define ClearPageReserved(page)	clear_bit(PG_reserved, &(page)->flags)
+#define __ClearPageReserved(page)	__clear_bit(PG_reserved, &(page)->flags)
 
 #define SetPagePrivate(page)	set_bit(PG_private, &(page)->flags)
 #define ClearPagePrivate(page)	clear_bit(PG_private, &(page)->flags)