[PATCH] Faster SWSUSP free page counting

[PATCH] Faster SWSUSP free page counting

[Nigel Cunningham]

Hi.

This patch improves the speed of SWSUSP's count_and_copy_data_pages
function by generating a map of the free pages before iterating through
the list of pages. The net result is to go from O(n^2) to O(n), if I
remember my computer science correctly.

Regards,

Nigel

diff -ruN linux-2.5.64-01-ide-disk-suspend/include/linux/page-flags.h linux-2.5.64-02-free-page-map/include/linux/page-flags.h
--- linux-2.5.64-01-ide-disk-suspend/include/linux/page-flags.h	2003-02-20 07:59:33.000000000 +1300
+++ linux-2.5.64-02-free-page-map/include/linux/page-flags.h	2003-03-18 10:56:13.000000000 +1200
@@ -74,6 +74,7 @@
 #define PG_mappedtodisk		17	/* Has blocks allocated on-disk */
 #define PG_reclaim		18	/* To be reclaimed asap */
 #define PG_compound		19	/* Part of a compound page */
+#define PG_free			20	/* swsusp - page is unused - dont rely on outside swsusp! */
 
 /*
  * Global page accounting.  One instance per CPU.  Only unsigned longs are
@@ -237,6 +238,10 @@
 #define ClearPageNosave(page)		clear_bit(PG_nosave, &(page)->flags)
 #define TestClearPageNosave(page)	test_and_clear_bit(PG_nosave, &(page)->flags)
 
+#define PageFree(page)		test_bit(PG_free, &(page)->flags)
+#define SetPageFree(page)	set_bit(PG_free, &(page)->flags)
+#define ClearPageFree(page)	clear_bit(PG_free, &(page)->flags)
+
 #define PageDirect(page)	test_bit(PG_direct, &(page)->flags)
 #define SetPageDirect(page)	set_bit(PG_direct, &(page)->flags)
 #define TestSetPageDirect(page)	test_and_set_bit(PG_direct, &(page)->flags)
diff -ruN linux-2.5.64-01-ide-disk-suspend/kernel/suspend.c linux-2.5.64-02-free-page-map/kernel/suspend.c
--- linux-2.5.64-01-ide-disk-suspend/kernel/suspend.c	2003-03-13 10:12:51.000000000 +1300
+++ linux-2.5.64-02-free-page-map/kernel/suspend.c	2003-03-18 10:54:31.000000000 +1200
@@ -479,6 +479,8 @@
 #else
 	BUG_ON (max_pfn != num_physpages);
 #endif
+	generate_free_page_map();
+
 	for (pfn = 0; pfn < max_pfn; pfn++) {
 		page = pfn_to_page(pfn);
 		if (PageHighMem(page))
diff -ruN linux-2.5.64-01-ide-disk-suspend/mm/page_alloc.c linux-2.5.64-02-free-page-map/mm/page_alloc.c
--- linux-2.5.64-01-ide-disk-suspend/mm/page_alloc.c	2003-02-20 07:59:34.000000000 +1300
+++ linux-2.5.64-02-free-page-map/mm/page_alloc.c	2003-03-18 10:53:22.000000000 +1200
@@ -387,26 +387,41 @@
 }
 
 #ifdef CONFIG_SOFTWARE_SUSPEND
-int is_head_of_free_region(struct page *page)
+void generate_free_page_map(void) 
 {
-        struct zone *zone = page_zone(page);
-        unsigned long flags;
-	int order;
+	int i, loop;
+	struct page * page;
+	unsigned long flags = 0;
+	unsigned int order;
 	struct list_head *curr;
+	struct zone *zone;
 
-	/*
-	 * Should not matter as we need quiescent system for
-	 * suspend anyway, but...
-	 */
-	spin_lock_irqsave(&zone->lock, flags);
-	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, list)) {
-				spin_unlock_irqrestore(&zone->lock, flags);
-				return 1 << order;
+	for(i=0; i < max_mapnr; i++)
+		ClearPageFree(mem_map+i);
+	
+	for_each_zone(zone) {
+		if (!zone->present_pages)
+			continue;
+
+		spin_lock_irqsave(&zone->lock, flags);
+		printk("Zone %8s ", zone->name);
+		for (order = 0; order < MAX_ORDER; ++order)
+			list_for_each(curr, &(zone->free_area[order].free_list)) {
+				if ((page = list_entry(curr, struct page, list)))
+					for(loop=0; loop < (1 << order); loop++)
+						SetPageFree(page+loop);
 			}
-	spin_unlock_irqrestore(&zone->lock, flags);
-        return 0;
+		spin_unlock_irqrestore(&zone->lock, flags);
+	}
+}
+
+int is_head_of_free_region(struct page *page)
+{
+	struct page * posn = page;
+
+	while (((posn-mem_map) < max_mapnr) && (PageFree(posn))) 
+		posn++;
+	return (posn - page);
 }
 
 /*

Re: [PATCH] Faster SWSUSP free page counting

[Pavel Machek]

Hi!

> This patch improves the speed of SWSUSP's count_and_copy_data_pages
> function by generating a map of the free pages before iterating through
> the list of pages. The net result is to go from O(n^2) to O(n), if I
> remember my computer science correctly.

Is the speed difference noticable?

If yes than okay, but generate_free_page_map() should still be moved
into kernel/suspend.c.
								Pavel
-- 
Horseback riding is like software...
...vgf orggre jura vgf serr.

Re: [PATCH] Faster SWSUSP free page counting

[Nigel Cunningham]

Hi.

The speed difference depends of course upon the number of pages free and
the degree of fragmentation. I guess the easy answer is that it was
written and kept because it helped. Having talked to Andrew about the
use of page flags, I'll do some more changes before we put it to Linus -
I'll use a dynamically allocated bitmap instead of pageflags.

Regards,

Nigel

On Tue, 2003-03-18 at 20:20, Pavel Machek wrote:
> Hi!
> 
> > This patch improves the speed of SWSUSP's count_and_copy_data_pages
> > function by generating a map of the free pages before iterating through
> > the list of pages. The net result is to go from O(n^2) to O(n), if I
> > remember my computer science correctly.
> 
> Is the speed difference noticable?
> 
> If yes than okay, but generate_free_page_map() should still be moved
> into kernel/suspend.c.
> 								Pavel
-- 
Nigel Cunningham
495 St Georges Road South, Hastings 4201, New Zealand

Be diligent to present yourself approved to God as a workman who does
not need to be ashamed, handling accurately the word of truth.
	-- 2 Timothy 2:14, NASB.