Skip to contentSkip to conversation

swsusp: Kill O(n^2) algorithm in swsusp

PATCH Pavel Machek 4 participants 4 messages Dec 25, 2004 – Dec 31, 2004

Subsystems (5)
lore
Share & tools
lore
#0 lore raw

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!
#1 lore raw

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
#2 lore raw
In reply to Pavel Machek

#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
#3 lore raw
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"