Skip to contentSkip to conversation

free bootmem feedback patch

PATCH Joshua Aas 6 participants 27 messages Jul 13, 2004 – Aug 6, 2004 Memory management

lore
Share & tools
lore

Joshua Aas

author
#0 lore raw

Hello,

NUMA machines with a lot of memory/nodes appear to hang when freeing boot memory, as it can take on the order of 4 minutes. I would like to propose this patch, which adds progress feedback during this time. On a machine with only one memory region (a single node), it prints:

Freeing boot memory... done

It prints more dots every x nodes handled based on the total number of nodes, in such a way that the line never exceeds 80 chars. This way it is possible to see progress being made. I have tested this on a few machines, including a 512p/512GB machine, and it works fine.

Please apply.

-----------------------------------------------------------------------

arch/ia64/mm/init.c 2004-07-13 15:25:46.000000000 -0500 renamed from arch/ia64/mm/init.c 2004-06-16 00:19:22.000000000 -0500 +22 -1
@@ -516,7 +516,7 @@ mem_init (void)
        long reserved_pages, codesize, datasize, initsize;
        unsigned long num_pgt_pages;
        pg_data_t *pgdat;
-       int i;
+       int i, pgdat_count;
        static struct kcore_list kcore_mem, kcore_vmem, kcore_kernel;
 
 #ifdef CONFIG_PCI
@@ -540,8 +540,29 @@ mem_init (void)
        kclist_add(&kcore_vmem, (void *)VMALLOC_START, VMALLOC_END-VMALLOC_START);
        kclist_add(&kcore_kernel, _stext, _end - _stext);
 
+       /*
+        * Give nice feedback while freeing boot memory. Each entry in pgdat corresponds to
+        * a memory zone, presumably a node in a NUMA machine. We need nice feedback so that 
+        * machines with lots of nodes/memory don't appear to be hanging.
+        */
+       printk(KERN_INFO "Freeing boot memory...");
+#      define NUM_FREE_BOOT_MEM_MSG_CHAR_COUNT 27 /* 22 + 5 for done message */
+       pgdat_count = 0;
+       i = 0;
        for_each_pgdat(pgdat)
+               pgdat_count++;
+       pgdat_count = (pgdat_count / (80 - NUM_FREE_BOOT_MEM_MSG_CHAR_COUNT)) - 1;
+       for_each_pgdat(pgdat) {
                totalram_pages += free_all_bootmem_node(pgdat);
+               if (i = pgdat_count) {
+                       printk(".");
+                       i = 0;
+               }
+               else {
+                       i++;
+               }
+       }
+       printk(" done\n");
 
        reserved_pages = 0;
        efi_memmap_walk(count_reserved_pages, &reserved_pages);

-----------------------------------------------------------------------

Signature · 4 lines
Josh Aas
Silicon Graphics, Inc. (SGI)
Linux System Software
651-683-3068
#1 lore raw
Quoted 3 lines

NUMA machines with a lot of memory/nodes appear to hang when freeing boot memory, as it can take on the order of 4 minutes.

Isn't this a feature of the amount of memory being freed, rather than the fact that there are many nodes? I.e. if someone has a single node box with a few TB of memory, they'll still have the multi-minute delay, but your patch won't give them any progress dots.

-Tony

author
#2 lore raw
In reply to Joshua Aas
Quoted 11 lines · Tony
Quoted 2 lines

NUMA machines with a lot of memory/nodes appear to hang when freeing boot memory, as it can take on the order of 4 minutes.

Isn't this a feature of the amount of memory being freed, rather than the fact that there are many nodes? I.e. if someone has a single node box with a few TB of memory, they'll still have the multi-minute delay, but your patch won't give them any progress dots.

-Tony

In the case of a single massive memory region you would still see "Freeing boot memory...", you just wouldn't see progress. That would make me feel better than nothing. It wouldn't be easy to add progress feedback within a single region without making one line of feedback per region - which seems like way too much to me on machines are at and above 128-256 regions. The way I've done it, single region machines get notification, multi-region machines see progress, and either way it only makes one line of feedback. Also, correct me if I'm wrong, but machines with 250GB-4TB or so of memory, where the pause is longest, are more likely to be multi-region machines.

Signature · 4 lines
Josh Aas
Silicon Graphics, Inc. (SGI)
Linux System Software
651-683-3068
#3 lore raw
In reply to Joshua Aas
Quoted 7 lines

Freeing boot memory... done

It prints more dots every x nodes handled based on the total number of nodes, in such a way that the line never exceeds 80 chars. This way it is possible to see progress being made. I have tested this on a few machines, including a 512p/512GB machine, and it works fine.

Better would be probably to speed this up.

I bet most of the overhead comes from taking locks in free_pages. How about adding a lockless ____free_pages and using that? Adding an more optimized path for this is also not out of the question.

Another way would be to increase the bootmem page size, but this won't cut down the overhead of free_pages.

-Andi

#4 lore raw
In reply to Joshua Aas
Quoted 9 lines · Joshua Aas

NUMA machines with a lot of memory/nodes appear to hang when freeing boot memory, as it can take on the order of 4 minutes. I would like to propose this patch, which adds progress feedback during this time. On a machine with only one memory region (a single node), it prints:
Freeing boot memory... done
It prints more dots every x nodes handled based on the total number of nodes, in such a way that the line never exceeds 80 chars. This way it is possible to see progress being made. I have tested this on a few machines, including a 512p/512GB machine, and it works fine.

Could I get a look at the memory map for this machine?

Also, it may make more sense to speed this up by freeing higher-order pages at a time.

-- wli

#5 lore raw
In reply to Joshua Aas
Quoted 5 lines · someone
Quoted 5 lines

Freeing boot memory... done
It prints more dots every x nodes handled based on the total number of nodes, in such a way that the line never exceeds 80 chars. This way it is possible to see progress being made. I have tested this on a few machines, including a 512p/512GB machine, and it works fine.

Quoted 6 lines · Andi Kleen

Better would be probably to speed this up.
I bet most of the overhead comes from taking locks in free_pages. How about adding a lockless ____free_pages and using that? Adding an more optimized path for this is also not out of the question. Another way would be to increase the bootmem page size, but this won't cut down the overhead of free_pages.

That also sounds like an excellent idea.

-- wli

author
#6 lore raw
In reply to Joshua Aas
Quoted 11 lines · Andi Kleen
Quoted 7 lines

Better would be probably to speed this up.
I bet most of the overhead comes from taking locks in free_pages. How about adding a lockless ____free_pages and using that? Adding an more optimized path for this is also not out of the question. Another way would be to increase the bootmem page size, but this won't cut down the overhead of free_pages.

That also sounds like an excellent idea.

Seems like a good idea to me too. I'll try to come up with a patch that doesn't do locking since it is early enough in the boot process, and maybe I can get rid of some looping/function calls too. This theoretical patch seems like a good idea in any case, but my progress patch might still be necessary on top of that since I'm not sure how much time it will actually save. On machines with 1-8TB of memory the wait might still be considerable (i.e. on the order of 3-8 minutes).

Signature · 4 lines
Josh Aas
Silicon Graphics, Inc. (SGI)
Linux System Software
651-683-3068
#7 lore raw
In reply to Joshua Aas

There are certainly some opportunities to speed up the code in free_all_bootmem_core() ... only one cpu is running, so using atomic operations to "ClearPageReserved(page)" is overkill. As is calling __free_page() [Which promptly tests that this isn't a reserved page, and does more atomic ops to decrement the count
from 1 (which we just set it to) to zero. What a waste of time!]

Quoted 2 lines

Also, it may make more sense to speed this up by freeing higher-order pages at a time.

This looks like the most promising way to put a major dent in the time taken. If you make sure that the bits in the bitmap line up correctly so that the physical addresses come out right, then you have an easy test for "if (v = ~0UL) {" to find larger order pages (5 on 32-bit systems, 6 on 64-bit). A factor 64 speedup would turn your 5 minute hang into a 5 second pause :-).

Some prefetches in that loop might help too (so you don't have to take a full L3 cache miss on every page structure).

Another approach might be to just free enough pages on each node to get all the cpus up and running, and then have one cpu on each node free the remaining pages for the node. But this sounds like major surgery (and wouldn't help my hypothetical machine that has huge memory on just one node).

-Tony

#8 lore raw
In reply to Joshua Aas
Quoted 2 lines · At some point in the past, I wrote:
Quoted 2 lines

Also, it may make more sense to speed this up by freeing higher-order pages at a time.

Quoted 5 lines · Tony

This looks like the most promising way to put a major dent in the time taken. If you make sure that the bits in the bitmap line up correctly so that the physical addresses come out right, then you have an easy test for "if (v = ~0UL) {" to find larger order pages (5 on 32-bit systems, 6 on 64-bit). A factor 64 speedup would

Quoted 8 lines

turn your 5 minute hang into a 5 second pause :-).
Some prefetches in that loop might help too (so you don't have to take a full L3 cache miss on every page structure). Another approach might be to just free enough pages on each node to get all the cpus up and running, and then have one cpu on each node free the remaining pages for the node. But this sounds like major surgery (and wouldn't help my hypothetical machine that has huge memory on just one node).

I'd even go so far as to suggest scanning the bitmap until the maximally sized higher-order page to free at the cursor (determined by cursor alignment and the first bit indicating a reserved page or otherwise MAX_ORDER bits out from the cursor) is found. More ideally (2.7) I'd prefer to rewrite the thing altogether and explicitly track ranges at all times, so eliminating all linear scans but the final one, which is then very natural to arrange to free maximally sized higher- order pages and has far fewer degenerate cases than the bitmaps.

Parallelization sounds very interesting, but something I don't have the machine and other resources to address. I suspect as node initialization is rearranged for the purpose of hotplugging memory this will become easier, but have no specific ideas (or even knowledge of what's going on) about the hotplug memory and/or bootmem parallelization topic, apart from believing it's a good idea.

-- wli

#9 lore raw
In reply to Joshua Aas
Quoted 4 lines · William Irwin

I'd even go so far as to suggest scanning the bitmap until the maximally sized higher-order page to free at the cursor (determined by cursor alignment and the first bit indicating a reserved page or otherwise MAX_ORDER bits out from the cursor) is found.

Attached is my version that just frees pages in O(log2(BITS_PER_LONG)) pieces ... because I'm too lazy to figure out all the boundary conditions to implement wli's excellent suggestion.

On my 2G machine, this reduced the time to free all the bootmem from 41ms to 18.1ms ... so it should shave some minutes off the monster SGI box that started this thread, but perhaps not enough to avoid the "looks like the system is hung" problem as you will still be looking at a couple of minutes :-( Since I only got a 55% reduction, rather than a factor of 64 I expect that modifying to look an larger order pages may have diminishing returns.

Notes and Caveats:
1) Is there a define someplace for log2(BITS_PER_LONG)? I couldn't find one, which is why I calculate the "order" in this patch.

2) On ia64 it looks like the pages and the bitmap are nicely aligned so that a longword in node_bootmem_map[] corresponds to an order 6 page with the right physical alignment. This may not be true on other architectures, and mm/bootmem.c is generic code. Before this patch can go into the base, someone would have to check all the other architectures (some of which might not care to change ... if they only support 4G or less, then the benefits of saving a few milliseconds during boot may not inspire them to mess with the boot code). For this reason I'm not adding a "Signed-off-by" to this patch because I don't want the flack for breaking other architectures ... but by all means take this patch and try it out.

I did also play with adding a "prefetchw(page + N)" to the original loop. With N>=6 the saving is about 5% for me. SGI might need a bigger N, and might see more savings, since most of the accesses here are to remote nodes. I didn't try this in my modified patch (the gains may be smaller as we don't do as much work in between touching each page).

-Tony

mm/bootmem.c +17 -1
diff -ru linux-2.6.8-rc1-orig/mm/bootmem.c linux-2.6.8-rc1/mm/bootmem.c
@@ -259,9 +259,12 @@
 	unsigned long i, count, total = 0;
 	unsigned long idx;
 	unsigned long *map; 
+	int order;
 
 	BUG_ON(!bdata->node_bootmem_map);
 
+	for (order = 0; (1 << order) < BITS_PER_LONG; order++)
+		;
 	count = 0;
 	/* first extant page of the node */
 	page = virt_to_page(phys_to_virt(bdata->node_boot_start));
@@ -269,7 +272,20 @@
 	map = bdata->node_bootmem_map;
 	for (i = 0; i < idx; ) {
 		unsigned long v = ~map[i / BITS_PER_LONG];
-		if (v) {
+		if (v == ~0UL) {
+			int j;
+
+			count += BITS_PER_LONG;
+			ClearPageReserved(page);
+			set_page_count(page, 1);
+			for (j = 1; j < BITS_PER_LONG; j++) {
+				ClearPageReserved(page + j);
+				set_page_count(page + j, 0);
+			}
+			__free_pages(page, order);
+			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) {
#10 lore raw
In reply to Joshua Aas
Quoted 3 lines · Tony

Notes and Caveats:
1) Is there a define someplace for log2(BITS_PER_LONG)? I couldn't find one, which is why I calculate the "order" in this patch.

ffs()?

Signature · 6 lines
"Next the statesmen will invent cheap lies, putting the blame upon 
the nation that is attacked, and every man will be glad of those
conscience-soothing falsities, and will diligently study them, and refuse
to examine any refutations of them; and thus he will by and by convince 
himself that the war is just, and will thank God for the better sleep 
he enjoys after this process of grotesque self-deception." -- Mark Twain
#11 lore raw
In reply to Joshua Aas
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line · Tony

Tony> Notes and Caveats: 1) Is there a define someplace for Tony> log2(BITS_PER_LONG)? I couldn't find one, which is why I Tony> calculate the "order" in this patch.

BITS_PER_LONG is a power-of-two, so ffs() will do. For more general cases, you may want asm/page.h:get_order() instead.

	--david
#12 lore raw
In reply to Joshua Aas
Quoted 10 lines · Tony

Attached is my version that just frees pages in O(log2(BITS_PER_LONG)) pieces ... because I'm too lazy to figure out all the boundary conditions to implement wli's excellent suggestion.
On my 2G machine, this reduced the time to free all the bootmem from 41ms to 18.1ms ... so it should shave some minutes off the monster SGI box that started this thread, but perhaps not enough to avoid the "looks like the system is hung" problem as you will still be looking at a couple of minutes :-( Since I only got a 55% reduction, rather than a factor of 64 I expect that modifying to look an larger order pages may have diminishing returns.

I'll work relative to this for the rest. I'd recommend using __ffs() instead of the loop. Also, combining this with a specialized page freeing function that doesn't e.g. fiddle with page references

Quoted 3 lines · Tony

Notes and Caveats:
1) Is there a define someplace for log2(BITS_PER_LONG)? I couldn't find one, which is why I calculate the "order" in this patch.

Unfortunately no. It would be nice to have one.

Quoted 11 lines · Tony

2) On ia64 it looks like the pages and the bitmap are nicely aligned so that a longword in node_bootmem_map[] corresponds to an order 6 page with the right physical alignment. This may not be true on other architectures, and mm/bootmem.c is generic code. Before this patch can go into the base, someone would have to check all the other architectures (some of which might not care to change ... if they only support 4G or less, then the benefits of saving a few milliseconds during boot may not inspire them to mess with the boot code). For this reason I'm not adding a "Signed-off-by" to this patch because I don't want the flack for breaking other architectures ... but by all means take this patch and try it out.

The common case is the bitmap and mem_map[] starting at 0. The remaining cases are pretty marginalized. This can actually be checked at runtime by checking the alignment of ->node_boot_start, e.g. maybe if (!~v && !((__pa(bdata->node_boot_start) >> PAGE_SHIFT) & ((1 << MAX_ORDER) - 1))) instead of just !~v.

-- wli

#13 lore raw
In reply to Joshua Aas
Quoted 6 lines · William Lee Irwin III
Quoted 3 lines · Tony

Notes and Caveats:
1) Is there a define someplace for log2(BITS_PER_LONG)? I couldn't find one, which is why I calculate the "order" in this patch.

Unfortunately no. It would be nice to have one.

#define log2(x) (ffs(x) - 1)

(ffs returns a value from 0 to 32 whereas log2 wants to return -1 to 31)

Obviously it rounds down, but that's entirely consistent with the behaviour of, say, 7/4 in C.

Signature · 6 lines
"Next the statesmen will invent cheap lies, putting the blame upon 
the nation that is attacked, and every man will be glad of those
conscience-soothing falsities, and will diligently study them, and refuse
to examine any refutations of them; and thus he will by and by convince 
himself that the war is just, and will thank God for the better sleep 
he enjoys after this process of grotesque self-deception." -- Mark Twain
#14 lore raw
In reply to Joshua Aas
Quoted 7 lines
Quoted 3 lines

still be looking at a couple of minutes :-( Since I only got a 55% reduction, rather than a factor of 64 I expect that modifying to look an larger order pages may have diminishing returns.

I'll work relative to this for the rest. I'd recommend using __ffs() instead of the loop. Also, combining this with a specialized page freeing function that doesn't e.g. fiddle with page references

The returns to freeing larger pages do indeed diminish fast. I added simple "look at the next word" and "look at the next three words" hacks to see what the times looked like with order=7 and order=8 ... and found that order 8 is only 1.8% faster than order 6.

Quoted 1 line

The common case is the bitmap and mem_map[] starting at 0.

Sadly not quite 0. PG_reserved is set for each page structure and must be cleared ... so we have to touch every page structure at least once :-( On a 4TB machine thats 0.25 billion cache misses (with a 16K page).

Quoted 5 lines

remaining cases are pretty marginalized. This can actually be checked at runtime by checking the alignment of ->node_boot_start, e.g. maybe if (!~v && !((__pa(bdata->node_boot_start) >> PAGE_SHIFT) & ((1 << MAX_ORDER) - 1)))
instead of just !~v.

That check can be done once (for each node) outside the loop. The exact expression used to set the "gofast" variable in my patch make need some tweaking

New patch attached.

-Tony

mm/bootmem.c +16 -1
@@ -259,6 +259,7 @@
 	unsigned long i, count, total = 0;
 	unsigned long idx;
 	unsigned long *map; 
+	int gofast = 0;
 
 	BUG_ON(!bdata->node_bootmem_map);
 
@@ -267,9 +268,23 @@
 	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;
+			ClearPageReserved(page);
+			set_page_count(page, 1);
+			for (j = 1; j < BITS_PER_LONG; j++)
+				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) {
#15 lore raw
In reply to Joshua Aas
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line · Matthew Wilcox

Matthew> #define log2(x) (ffs(x) - 1)

At the risk of pointing out the obvious, this definition only works for integer-powers of two...

get_order() works for any "unsigned long" value.

	--david
#16 lore raw
In reply to Joshua Aas
Quoted 1 line · William Lee Irwin III
Quoted 1 line

Unfortunately no. It would be nice to have one.

Quoted 4 lines · Matthew Wilcox

#define log2(x) (ffs(x) - 1)
(ffs returns a value from 0 to 32 whereas log2 wants to return -1 to 31) Obviously it rounds down, but that's entirely consistent with the behaviour of, say, 7/4 in C.

The kernel uses __ffs(), which returns from 0 to 31 and is undefined on 0. Its rounding behavior is wrong for log2(). Anyhow, we happen to know it's a power of 2 and that __ffs() will do.

-- wli

#17 lore raw
In reply to Joshua Aas
Quoted 8 lines · David Mosberger
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line · Matthew Wilcox

Matthew> #define log2(x) (ffs(x) - 1)

At the risk of pointing out the obvious, this definition only works for integer-powers of two...

get_order() works for any "unsigned long" value.

Oh, um, I didn't realise that ffs() worked backwards. fls() - 1, then.

Signature · 6 lines
"Next the statesmen will invent cheap lies, putting the blame upon 
the nation that is attacked, and every man will be glad of those
conscience-soothing falsities, and will diligently study them, and refuse
to examine any refutations of them; and thus he will by and by convince 
himself that the war is just, and will thank God for the better sleep 
he enjoys after this process of grotesque self-deception." -- Mark Twain
#18 lore raw
In reply to Joshua Aas
Quoted 3 lines · At some point in the past, I wrote:
Quoted 3 lines

I'll work relative to this for the rest. I'd recommend using __ffs() instead of the loop. Also, combining this with a specialized page freeing function that doesn't e.g. fiddle with page references

Quoted 5 lines · Tony

The returns to freeing larger pages do indeed diminish fast. I added simple "look at the next word" and "look at the next three words" hacks to see what the times looked like with order=7 and order=8 ... and found that order 8 is only 1.8% faster than order 6.

This is likely explained by the differences in remaining buddy bitmap depth.

Quoted 1 line · At some point in the past, I wrote:
Quoted 1 line

The common case is the bitmap and mem_map[] starting at 0.

Quoted 4 lines · Tony

Sadly not quite 0. PG_reserved is set for each page structure and must be cleared ... so we have to touch every page structure at least once :-( On a 4TB machine thats 0.25 billion cache misses (with a 16K page).

I had more in mind that PC's etc. had mem_map[]/etc. starting at 0.

Moving on, free_area_init_core() makes a rather pessimal assumption and sets all pages reserved and all refcounts to 0. Setting the refcounts to 0 is okay, but needs an entrypoint exported that can free such pages, likely worth implementing in tandem with lockfree freeing. In this arrangement, the entire bitmap needs iterating over to mark the pages that aren't going to be freed reserved.

Quoted 5 lines · At some point in the past, I wrote:
Quoted 5 lines

remaining cases are pretty marginalized. This can actually be checked at runtime by checking the alignment of ->node_boot_start, e.g. maybe if (!~v && !((__pa(bdata->node_boot_start) >> PAGE_SHIFT) & ((1 << MAX_ORDER) - 1)))
instead of just !~v.

Quoted 4 lines · Tony

That check can be done once (for each node) outside the loop. The exact expression used to set the "gofast" variable in my patch make need some tweaking
New patch attached.

I presumed enough compiler QOI for loop invariant hoisting, which I suppose is a mistake with gcc.

-- wli

author
#19 lore raw
In reply to Joshua Aas

Are there any outstanding issues with Tony's second revision of the free_all_bootmem_core function? Do we still have the problem of making sure longwork in node_bootmem_map[] corresponds to an order 6 page with the right physical alignment? The second revision looks good to me. If I could get some more feedback on it I'll clean up any remaining issues so it can land sometime soon. I'll post test results (unpatched vs. patched) on a big machine later this afternoon.

wli - do you still want to see the memory map for my big test machine (512GB RAM)?

-Josh

Quoted 40 lines · Tony
Quoted 7 lines
Quoted 3 lines

still be looking at a couple of minutes :-( Since I only got a 55% reduction, rather than a factor of 64 I expect that modifying to look an larger order pages may have diminishing returns.

I'll work relative to this for the rest. I'd recommend using __ffs() instead of the loop. Also, combining this with a specialized page freeing function that doesn't e.g. fiddle with page references

The returns to freeing larger pages do indeed diminish fast. I added simple "look at the next word" and "look at the next three words" hacks to see what the times looked like with order=7 and order=8 ... and found that order 8 is only 1.8% faster than order 6.

Quoted 1 line

The common case is the bitmap and mem_map[] starting at 0.

Sadly not quite 0. PG_reserved is set for each page structure and must be cleared ... so we have to touch every page structure at least once :-( On a 4TB machine thats 0.25 billion cache misses (with a 16K page).

Quoted 5 lines

remaining cases are pretty marginalized. This can actually be checked at runtime by checking the alignment of ->node_boot_start, e.g. maybe if (!~v && !((__pa(bdata->node_boot_start) >> PAGE_SHIFT) & ((1 << MAX_ORDER) - 1)))
instead of just !~v.

That check can be done once (for each node) outside the loop. The exact expression used to set the "gofast" variable in my patch make need some tweaking

New patch attached.

-Tony

Signature · 4 lines
Josh Aas
Silicon Graphics, Inc. (SGI)
Linux System Software
651-683-3068
#20 lore raw
In reply to Joshua Aas
Quoted 7 lines · Josh Aas

Are there any outstanding issues with Tony's second revision of the free_all_bootmem_core function? Do we still have the problem of making sure longwork in node_bootmem_map[] corresponds to an order 6 page with the right physical alignment? The second revision looks good to me. If I could get some more feedback on it I'll clean up any remaining issues so it can land sometime soon. I'll post test results (unpatched vs. patched) on a big machine later this afternoon.

I think it's fine.

Quoted 2 lines · Josh Aas

wli - do you still want to see the memory map for my big test machine (512GB RAM)?

Sure.

-- wli

author
#21 lore raw
In reply to Joshua Aas

Attached is an improved version of Tony Luck's patch. It shaves another ~25% off by not using atomic ops to clear the page reserved bits and prefetching. Tony - will you sign off on it with me and we'll get this in?

Unfortunately, this still leaves a ~1 minute delay with no indication of what is going on for 4TB machines, and ~2 minutes for 8TB. Thus, I'd still like to see my progrees indicator patch go in. I am guessing memory sizes are only going to get bigger than even 8 TB, and memory is not going to get faster at the rate the totals increase (it certainly didn't double in speed between 4 and 8 TB installations). Thoughts?

-Josh

Quoted 16 lines · William Lee Irwin III
Quoted 1 line · Josh Aas

Are there any outstanding issues with Tony's second revision of the free_all_bootmem_core function? Do we still have the problem of making sure longwork in node_bootmem_map[] corresponds to an order 6 page with the right physical alignment? The second revision looks good to me. If I could get some more feedback on it I'll clean up any remaining issues so it can land sometime soon. I'll post test results (unpatched vs. patched) on a big machine later this afternoon.

I think it's fine.

Quoted 1 line · Josh Aas

wli - do you still want to see the memory map for my big test machine (512GB RAM)?

Sure.

-- wli

Signature · 4 lines
Josh Aas
Silicon Graphics, Inc. (SGI)
Linux System Software
651-683-3068
mm/bootmem.c +21 -2
@@ -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;
+			(page)->flags &= ~(1UL << PG_reserved);
+			set_page_count(page, 1);
+			for (j = 1; j < BITS_PER_LONG; j++) {
+				if (j + 16 < BITS_PER_LONG) {
+                      			prefetchw(page + j + 16);
+                                }
+				(page + j)->flags &= ~(1UL << PG_reserved);
+			}	
+			__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);
+					(page)->flags &= ~(1UL << PG_reserved);	
 					set_page_count(page, 1);
 					__free_page(page);
 				}
#22 lore raw
In reply to Joshua Aas
Quoted 10 lines · Josh Aas

Attached is an improved version of Tony Luck's patch. It shaves another ~25% off by not using atomic ops to clear the page reserved bits and prefetching. Tony - will you sign off on it with me and we'll get this in? Unfortunately, this still leaves a ~1 minute delay with no indication of what is going on for 4TB machines, and ~2 minutes for 8TB. Thus, I'd still like to see my progrees indicator patch go in. I am guessing memory sizes are only going to get bigger than even 8 TB, and memory is not going to get faster at the rate the totals increase (it certainly didn't double in speed between 4 and 8 TB installations). Thoughts?

There are still stronger attacks on this problem. I'll go about porting one or more of those up to current. (The one I'm favoring at the moment has actually never had broad exposure in the past).

This will be a time-consuming affair, so it will be fine to merge things like this in the interim. I would give an ETA of several weeks for an initial release, largely for testing on a sufficiently broad variety of architectures beforehand.

-- wli

#23 lore raw
In reply to Joshua Aas
Quoted 4 lines · Josh Aas

Attached is an improved version of Tony Luck's patch. It shaves another ~25% off by not using atomic ops to clear the page reserved bits and prefetching. Tony - will you sign off on it with me and we'll get this in?

Does the change:
- ClearPageReserved(page);
+ (page)->flags &= ~(1UL << PG_reserved);

in the "else if (v)" clause actually make any difference? I would expect not (unless you have bizarrely fragmented memory), so you could just leave the atomic operations there.

But it might be prettier to define a BootClearPageReserved() function in page-flags.h rather than expose the details of the implementation here in bootmem.c (in which case you could use this new function in the "else if (v)" clause too for symmetry).

Finally you have a magic "16" in the prefetchw() path. Where did it come from, and is it the right number for non-ia64 machines?

Here's a "Signed-off-by: Tony Luck <[email protected]>" that you can cut-n-paste onto the patch when you repost to LKML.

Quoted 3 lines

Unfortunately, this still leaves a ~1 minute delay with no indication of what is going on for 4TB machines, and ~2 minutes for 8TB.

Agreed that's long enough to cause worry, concern, even panic amongst nervous system administrators. But I think that wli will hack this time down a lot more when he gets his patch together. So I'd like to wait and see what that looks like before I add the progress dots patch.

-Tony

author
#24 lore raw
In reply to Joshua Aas
Quoted 7 lines · Tony

Does the change:

(quoted diff) +1 -1
-			ClearPageReserved(page);
+			(page)->flags &= ~(1UL << PG_reserved);

in the "else if (v)" clause actually make any difference? I would expect not (unless you have bizarrely fragmented memory), so you could just leave the atomic operations there.

I imagine that change would make an improvement, no matter how small it is. Why not just do it? Especially after I define a macro.

Quoted 4 lines

But it might be prettier to define a BootClearPageReserved() function in page-flags.h rather than expose the details of the implementation here in bootmem.c (in which case you could use this new function in the "else if (v)" clause too for symmetry).

I'll go ahead and create a macro for the non-atomic bit clear. Perhaps call it "ClearPageReservedNoAtomic" instead of "BootClearPageReserved"?

Quoted 2 lines

Finally you have a magic "16" in the prefetchw() path. Where did it come from, and is it the right number for non-ia64 machines?

My bad for not explaining that. In my limited testing of this particular number it seemed to be the sweet spot for prefetching. I think it is a good number for all architectures because 32 bit architectures won't need the speed boost as much as 64 bit architectures. They are not likely to have > 4GB memory,, in which case this function's time is probably less than 1 second anyway. So even though you have to wait 16 iterations before you start getting the prefetched advantage, 32 bit architectures still get the improvement on half the iterations. It should be good for other 64 bit architectures because all architectures should be able to complete the prefetch by the 16th iteration, and all 64 bit architectures will get the prefetched advantage in 48/64 iterations (that might be OBO but whatever). I haven't used any 64 bit machines other than ia64 (or used prefetching before for that matter), so let me know if my logic is wrong. I do think that number could be tuned to a slightly better value, but 16 is nice and safe for now. And I only have ia64 boxes around.

Quoted 2 lines

Here's a "Signed-off-by: Tony Luck <[email protected]>" that you can cut-n-paste onto the patch when you repost to LKML.

Thanks.

Quoted 10 lines
Quoted 3 lines

Unfortunately, this still leaves a ~1 minute delay with no indication of what is going on for 4TB machines, and ~2 minutes for 8TB.

Agreed that's long enough to cause worry, concern, even panic amongst nervous system administrators. But I think that wli will hack this time down a lot more when he gets his patch together. So I'd like to wait and see what that looks like before I add the progress dots patch.

Sounds good.

Signature · 4 lines
Josh Aas
Silicon Graphics, Inc. (SGI)
Linux System Software
651-683-3068
#25 lore raw
In reply to Joshua Aas
Quoted 2 lines

I'll go ahead and create a macro for the non-atomic bit clear. Perhaps call it "ClearPageReservedNoAtomic" instead of "BootClearPageReserved"?

That looks like a more meaningful name than my suggestion.

Quoted 9 lines
Quoted 2 lines

Finally you have a magic "16" in the prefetchw() path. Where did it come from, and is it the right number for non-ia64 machines?

My bad for not explaining that. In my limited testing of this particular number it seemed to be the sweet spot for prefetching. I think it is a good number for all architectures because 32 bit architectures won't need the speed boost as much as 64 bit architectures. They are not likely to have > 4GB memory,, in which case this function's time is probably less than 1 second anyway.

There are quite a few x86 boxes running with 16GB ... but the max is 64GB, which is still below the pain threshold for seeing an unreasonable delay during this routine ... so I agree that perfect tuning is irrelevent for 32-bit machines here. You should include your explanatory paragraph when you post to LKML.

-Tony

#26 lore raw
In reply to Joshua Aas
Quoted 6 lines · Josh Aas
Quoted 6 lines

My bad for not explaining that. In my limited testing of this particular number it seemed to be the sweet spot for prefetching. I think it is a good number for all architectures because 32 bit architectures won't need the speed boost as much as 64 bit architectures. They are not likely to have > 4GB memory,, in which case this function's time is probably less than 1 second anyway.

Quoted 5 lines · Tony

There are quite a few x86 boxes running with 16GB ... but the max is 64GB, which is still below the pain threshold for seeing an unreasonable delay during this routine ... so I agree that perfect tuning is irrelevent for 32-bit machines here. You should include your explanatory paragraph when you post to LKML.

The 32-bit situation is even more unusual than that. Bootmem is only used for ZONE_NORMAL, the region of physical memory usually mapped into the majority of kernel virtualspace. So even while physical memory may span 64GB, no more than 896MB or so are ever tracked by the bootmem allocator. ->zone_mem_map for highmem zones is set up later by hand.

-- wli