swsusp: Kill O(n^2) algorithm in swsusp
Subsystems (5)
Hi!
Some machines are spending minutes of CPU time during suspend in stupid O(n^2) algorithm. This patch replaces it with O(n) algorithm, making swsusp usable to some people.
I'd like people to test this. It should probably spend few weeks in -mm tree to get some beating. OTOH SUSE has variant of this patch in its kernel.
Pavel
include/linux/page-flags.h +5 -1
@@ -74,7 +74,7 @@#define PG_swapcache 16/* Swap page: swp_entry_t in private */ #define PG_mappedtodisk 17/* Has blocks allocated on-disk */ #define PG_reclaim 18/* To be reclaimed asap */ - +#define PG_nosave_free 19/* Page is free and should not be written */ /* * Global page accounting. One instance per CPU. Only unsigned longs are
@@ -277,6 +277,10 @@#define ClearPageNosave (page) clear_bit(PG_nosave, &(page)->flags)#define TestClearPageNosave (page) test_and_clear_bit(PG_nosave, &(page)->flags) +#define PageNosaveFree (page) test_bit(PG_nosave_free, &(page)->flags) +#define SetPageNosaveFree (page) set_bit(PG_nosave_free, &(page)->flags) +#define ClearPageNosaveFree (page) clear_bit(PG_nosave_free, &(page)->flags) +#define PageMappedToDisk (page) test_bit(PG_mappedtodisk, &(page)->flags)#define SetPageMappedToDisk (page) set_bit(PG_mappedtodisk, &(page)->flags)#define ClearPageMappedToDisk (page) clear_bit(PG_mappedtodisk, &(page)->flags)
include/linux/suspend.h +1 -0
@@ -31,6 +31,7 @@/* mm/page_alloc.c */ extern void drain_local_pages (void ); +extern void mark_free_pages (struct zone *zone);/* kernel/power/swsusp.c */ extern int software_suspend (void );
kernel/power/swsusp.c +56 -75
222 lines not on this page · raw message
mm/page_alloc.c +17 -13
@@ -437,26 +437,30 @@#endif /* CONFIG_PM || CONFIG_HOTPLUG_CPU */ #ifdef CONFIG_PM -int is_head_of_free_region (struct page *page) + +void mark_free_pages (struct zone *zone) { -struct zone *zone =page_zone (page); -unsigned long flags; +unsigned long zone_pfn, flags;int order;struct list_head *curr; -/* -* Should not matter as we need quiescent system for -* suspend anyway, but... -*/ +if (!zone->spanned_pages) +return ; +spin_lock_irqsave (&zone->lock, flags); +for (zone_pfn =0 ; zone_pfn < zone->spanned_pages; ++zone_pfn) +ClearPageNosaveFree (pfn_to_page (zone_pfn + zone->zone_start_pfn)); +for (order =MAX_ORDER -1 ; order >=0 ; --order) -list_for_each (curr, &zone->free_area[order].free_list) - if (page == list_entry(curr, struct page, lru)) { -spin_unlock_irqrestore (&zone->lock, flags); -return 1 << order; - } +list_for_each (curr, &zone->free_area[order].free_list) { +unsigned long start_pfn, i; + + start_pfn = page_to_pfn(list_entry(curr, struct page, lru)); + +for (i=0 ; i < (1 <<order); i++) +SetPageNosaveFree (pfn_to_page (start_pfn+i)); + }spin_unlock_irqrestore (&zone->lock, flags); -return 0 ; }/*
Signature · 2 lines
People were complaining that M$ turns users into beta-testers... ...jr ghea gurz vagb qrirybcref, naq gurl frrz gb yvxr vg gung jnl!
The patch is really too good.
My comp now suspends in around 5seconds. Before patching, it took around a minute (sometimes more). Hats off to you.
Details (if you care)
#uname -a
Linux rajsekar.pc 2.6.10-rc1-ck1-reiser4 #3 Fri Dec 31 07:47:32 IST 2004 i686 AuthenticAMD unknown GNU/Linux
Tell me if you want me to test anything else.
Signature · 1 line
Rajsekar
#include <hallo.h>
Quoted 7 lines · Pavel Machek
Hi!
Some machines are spending minutes of CPU time during suspend in stupid O(n^2) algorithm. This patch replaces it with O(n) algorithm, making swsusp usable to some people.
I'd like people to test this. It should probably spend few weeks
Has been working quite stable for some days now (and countless reboots) with kernel 2.6.9. And is as fast as swsusp2 (but works reliable ;-).
Regards,
Eduard.
Signature · 1 line
In the beginning was the word, and the word was content-type: text/plain
Quoted 4 lines · Eduard Bloch
#include <
hallo.h>Quoted 2 lines · Pavel Machek
Hi!
Quoted 8 lines
Quoted 5 lines
Some machines are spending minutes of CPU time during suspend in stupid O(n^2) algorithm. This patch replaces it with O(n) algorithm, making swsusp usable to some people.
I'd like people to test this. It should probably spend few weeks
Has been working quite stable for some days now (and countless reboots) with kernel 2.6.9. And is as fast as swsusp2 (but works reliable ;-).
Confirmed. I've been running it for quite some time with 2.6.10 on an AMD64 and it works great.
Greets,
RJW
Signature · 3 lines
- Would you tell me, please, which way I ought to go from here? - That depends a good deal on where you want to get to. -- Lewis Carroll "Alice's Adventures in Wonderland"