* swsusp: remove O(n^2) algorithm in page relocation
@ 2005-01-16 23:42 Pavel Machek
0 siblings, 0 replies; only message in thread
From: Pavel Machek @ 2005-01-16 23:42 UTC (permalink / raw)
To: xhejtman, Andrew Morton, kernel list
Hi!
This removes another O(n^2) algorithm from page relocation in
swsusp. Relocation took as long as reading pages from disk on my
machine, and it took minutes for some poor testers. Please apply,
Pavel
From: Lukas Hejtmanek <xhejtman@mail.muni.cz>
Signed-off-by: Pavel Machek <pavel@suse.cz>
--- linux-cvs/kernel/power/swsusp.c 2005-01-16 22:29:25.000000000 +0100
+++ linux/kernel/power/swsusp.c 2005-01-16 23:10:29.000000000 +0100
@@ -893,26 +893,18 @@
return error;
}
-
-
/* More restore stuff */
-#define does_collide(addr) does_collide_order(pagedir_nosave, addr, 0)
-
/*
* Returns true if given address/order collides with any orig_address
*/
-static int __init does_collide_order(suspend_pagedir_t *pagedir, unsigned long addr,
- int order)
+static int __init does_collide_order(unsigned long addr, int order)
{
int i;
- unsigned long addre = addr + (PAGE_SIZE<<order);
- for (i=0; i < nr_copy_pages; i++)
- if ((pagedir+i)->orig_address >= addr &&
- (pagedir+i)->orig_address < addre)
+ for (i=0; i < (1<<order); i++)
+ if (!PageNosaveFree(virt_to_page(addr + i * PAGE_SIZE)))
return 1;
-
return 0;
}
@@ -931,7 +923,7 @@
addr = get_zeroed_page(GFP_ATOMIC);
if(!addr)
return -ENOMEM;
- } while (does_collide(addr));
+ } while (does_collide_order(addr, 0));
(pagedir_nosave+i)->address = addr;
}
@@ -948,16 +940,34 @@
void **eaten_memory = NULL;
void **c = eaten_memory, *m, *f;
int ret = 0;
+ struct zone *zone;
+ int i;
+ struct pbe *p;
+ unsigned long zone_pfn;
printk("Relocating pagedir ");
- if (!does_collide_order(old_pagedir, (unsigned long)old_pagedir, pagedir_order)) {
+ /* Set page flags */
+
+ for_each_zone(zone) {
+ for (zone_pfn = 0; zone_pfn < zone->spanned_pages; ++zone_pfn)
+ SetPageNosaveFree(pfn_to_page(zone_pfn +
+ zone->zone_start_pfn));
+ }
+
+ /* Clear orig address */
+
+ for(i = 0, p = pagedir_nosave; i < nr_copy_pages; i++, p++) {
+ ClearPageNosaveFree(virt_to_page(p->orig_address));
+ }
+
+ if (!does_collide_order((unsigned long)old_pagedir, pagedir_order)) {
printk("not necessary\n");
return check_pagedir();
}
while ((m = (void *) __get_free_pages(GFP_ATOMIC, pagedir_order)) != NULL) {
- if (!does_collide_order(old_pagedir, (unsigned long)m, pagedir_order))
+ if (!does_collide_order((unsigned long)m, pagedir_order))
break;
eaten_memory = m;
printk( "." );
--
People were complaining that M$ turns users into beta-testers...
...jr ghea gurz vagb qrirybcref, naq gurl frrz gb yvxr vg gung jnl!
^ permalink raw reply [flat|nested] only message in thread
only message in thread, other threads:[~2005-01-16 23:43 UTC | newest]
Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2005-01-16 23:42 swsusp: remove O(n^2) algorithm in page relocation Pavel Machek
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).