lkml.org 
[lkml]   [2003]   [Mar]   [17]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
Date
From
Subject[PATCH] Faster SWSUSP free page counting
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);
}

/*


-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

\
 
 \ /
  Last update: 2005-03-22 13:34    [W:0.021 / U:4.840 seconds]
©2003-2018 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site