Use extents for recording what swap is allocated.
Subsystems (2)
PATCH 1/1 Use extents for recording what swap is allocated.
Switch from bitmaps to using extents to record what swap is allocated; they make more efficient use of memory, particularly where the allocated storage is small and the swap space is large.
This is also part of the ground work for implementing support for supporting multiple swap devices.
kernel/power/Makefile +1 -1
@@ -5,6 +5,6 @@ endif obj-y := main.o process.o console.o obj-$(CONFIG_PM_LEGACY) += pm.o -obj-$(CONFIG_SOFTWARE_SUSPEND) += swsusp.o disk.o snapshot.o swap.o user.o +obj-$(CONFIG_SOFTWARE_SUSPEND) += swsusp.o disk.o snapshot.o swap.o user.o extent.o obj-$(CONFIG_MAGIC_SYSRQ) += poweroff.o
kernel/power/extent.c new file +119 -0
119 lines not on this page · raw message
kernel/power/extent.h new file +50 -0
50 lines not on this page · raw message
kernel/power/power.h +4 -24
@@ -1,6 +1,8 @@#include <linux/suspend.h> #include <linux/utsname.h> +#include "extent.h" +struct swsusp_info {struct new_utsname uts;u32 version_code;
@@ -119,30 +121,8 @@ #define SNAPSHOT_SET_SWAP_FILE _IOW(SNA#define SNAPSHOT_S2RAM _IO(SNAPSHOT_IOC_MAGIC, 11)#define SNAPSHOT_IOC_MAXNR 11 -/** -* The bitmap is used for tracing allocated swap pages -* -* The entire bitmap consists of a number of bitmap_page -* structures linked with the help of the .next member. -* Thus each page can be allocated individually, so we only -* need to make 0-order memory allocations to create -* the bitmap. -*/ - -#define BITMAP_PAGE_SIZE (PAGE_SIZE - sizeof(void *)) -#define BITMAP_PAGE_CHUNKS (BITMAP_PAGE_SIZE / sizeof(long)) -#define BITS_PER_CHUNK (sizeof(long) * 8) -#define BITMAP_PAGE_BITS (BITMAP_PAGE_CHUNKS * BITS_PER_CHUNK) - -struct bitmap_page { -unsigned long chunks[BITMAP_PAGE_CHUNKS ]; -struct bitmap_page *next; -}; - -extern void free_bitmap (struct bitmap_page *bitmap); -extern struct bitmap_page *alloc_bitmap (unsigned int nr_bits); -extern unsigned long alloc_swap_page (int swap,struct bitmap_page *bitmap); -extern void free_all_swap_pages (int swap,struct bitmap_page *bitmap); +extern unsigned long alloc_swap_page (int swap,struct extent_chain *extents); +extern void free_all_swap_pages (int swap,struct extent_chain *extents);extern int swsusp_check (void );extern int swsusp_shrink_memory (void );
kernel/power/swap.c +6 -13
@@ -152,7 +152,7 @@ struct swap_map_page {struct swap_map_handle {struct swap_map_page *cur;unsigned long cur_swap; -struct bitmap_page *bitmap; +struct extent_chain extents;unsigned int k; };
@@ -161,9 +161,6 @@ static void release_swap_writer(struct sif (handle->cur)free_page ((unsigned long )handle->cur); handle->cur =NULL ; -if (handle->bitmap) -free_bitmap (handle->bitmap); - handle->bitmap =NULL ; } static void show_speed(struct timeval *start, struct timeval *stop,
@@ -191,12 +188,8 @@ static int get_swap_writer(struct swap_m handle->cur = (struct swap_map_page *)get_zeroed_page (GFP_KERNEL );if (!handle->cur)return -ENOMEM ; - handle->bitmap =alloc_bitmap (count_swap_pages (root_swap,0 )); -if (!handle->bitmap) { -release_swap_writer (handle); -return -ENOMEM ; - } - handle->cur_swap =alloc_swap_page (root_swap, handle->bitmap); +memset (&handle->extents,0 ,sizeof (struct extent_chain )); + handle->cur_swap =alloc_swap_page (root_swap, &handle->extents);if (!handle->cur_swap) {release_swap_writer (handle);return -ENOSPC ;
@@ -241,7 +234,7 @@ static int swap_write_page(struct swap_mif (!handle->cur)return -EINVAL ; - offset =alloc_swap_page (root_swap, handle->bitmap); + offset =alloc_swap_page (root_swap, &handle->extents); error =write_page (buf, offset, bio_chain);if (error)return error;
@@ -250,7 +243,7 @@ static int swap_write_page(struct swap_m error =wait_on_bio_chain (bio_chain);if (error) goto out; - offset =alloc_swap_page (root_swap, handle->bitmap); + offset =alloc_swap_page (root_swap, &handle->extents);if (!offset)return -ENOSPC ; handle->cur->next_swap = offset;
@@ -379,7 +372,7 @@ int swsusp_write(void) } }if (error) -free_all_swap_pages (root_swap, handle.bitmap); +free_all_swap_pages (root_swap, &handle.extents);release_swap_writer (&handle);return error; }
kernel/power/swsusp.c +18 -83
120 lines not on this page · raw message
kernel/power/user.c +6 -16
@@ -32,7 +32,7 @@ #define SNAPSHOT_MINOR 231 static struct snapshot_data { struct snapshot_handle handle; int swap; - struct bitmap_page *bitmap; + struct extent_chain extents; int mode; char frozen; char ready;
@@ -61,7 +61,7 @@ static int snapshot_open(struct inode *i data->swap =-1 ; data->mode =O_WRONLY ; } - data->bitmap =NULL ; +memset (&data->extents,0 ,sizeof (struct extent_chain )); data->frozen =0 ; data->ready =0 ;
@@ -74,8 +74,7 @@ static int snapshot_release(struct inodeswsusp_free (); data = filp->private_data; -free_all_swap_pages (data->swap, data->bitmap); -free_bitmap (data->bitmap); +free_all_swap_pages (data->swap, &data->extents);if (data->frozen) {down (&pm_sem);thaw_processes ();
@@ -232,14 +231,7 @@ static int snapshot_ioctl(struct inode * error = -ENODEV ;break ; } -if (!data->bitmap) { - data->bitmap =alloc_bitmap (count_swap_pages (data->swap,0 )); -if (!data->bitmap) { - error = -ENOMEM ; -break ; - } - } - offset =alloc_swap_page (data->swap, data->bitmap); + offset =alloc_swap_page (data->swap, &data->extents);if (offset) { offset <<=PAGE_SHIFT ; error =put_user (offset, (loff_t __user *)arg);
@@ -253,13 +245,11 @@ static int snapshot_ioctl(struct inode * error = -ENODEV ;break ; } -free_all_swap_pages (data->swap, data->bitmap); -free_bitmap (data->bitmap); - data->bitmap =NULL ; +free_all_swap_pages (data->swap, &data->extents);break ;case SNAPSHOT_SET_SWAP_FILE : -if (!data->bitmap) { +if (!data->extents.size) {/* * User space encodes device types as two-byte values, * so we need to recode them
Hi!
Quoted 6 lines
Switch from bitmaps to using extents to record what swap is allocated; they make more efficient use of memory, particularly where the allocated storage is small and the swap space is large.
This is also part of the ground work for implementing support for supporting multiple swap devices.
bitmaps were more efficient and longer than original code... I did not _like_ them, but they are in now. I'd hate to change the code again, for what, 0.5% gain?
...and this is still longer than bitmaps.
And SNAPSHOT_GET_SWAP_PAGE seems to support multiple swap spaces already.
Pavel
Signature · 2 lines
(english) http://www.livejournal.com/~pavelmachek (cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html
Hi.
Quoted 6 lines · Pavel Machek
Hi!
Quoted 3 lines
Switch from bitmaps to using extents to record what swap is allocated; they make more efficient use of memory, particularly where the allocated storage is small and the swap space is large.
Quoted 6 lines
Quoted 2 lines
This is also part of the ground work for implementing support for supporting multiple swap devices.
bitmaps were more efficient and longer than original code... I did not _like_ them, but they are in now. I'd hate to change the code again, for what, 0.5% gain?
0.5% of what? This is part of what is needed to implement support for multiple swap devices. You could extend what you already have, implementing bitmaps that require a bit for every page of swap the user has swapon'd, but that doesn't seem efficient to me.
Quoted 4 lines
...and this is still longer than bitmaps.
And
SNAPSHOT_GET_SWAP_PAGEseems to support multiple swap spaces already.
It may do, but swap.c certainly doesn't. It supports exactly one device.
Regards,
Nigel
Quoted 12 lines · Nigel Cunningham
Hi.
Quoted 9 lines · Pavel Machek
Hi!
Quoted 6 lines
Switch from bitmaps to using extents to record what swap is allocated; they make more efficient use of memory, particularly where the allocated storage is small and the swap space is large.
This is also part of the ground work for implementing support for supporting multiple swap devices.
Quoted 8 lines
Quoted 3 lines
bitmaps were more efficient and longer than original code... I did not _like_ them, but they are in now. I'd hate to change the code again, for what, 0.5% gain?
0.5% of what? This is part of what is needed to implement support for multiple swap devices. You could extend what you already have, implementing bitmaps that require a bit for every page of swap the user has swapon'd, but that doesn't seem efficient to me.
I agree. Further, I though I would change the bitmaps thing at some point, but there still are more urgent things to do. ;-)
Quoted 1 line
Quoted 1 line
...and this is still longer than bitmaps.
Yes, it is. Still I'd like to have a thorough look at it. The idea is fine by me.
Quoted 4 lines
Quoted 2 lines
And
SNAPSHOT_GET_SWAP_PAGEseems to support multiple swap spaces already.It may do, but
swap.ccertainly doesn't. It supports exactly one device.
That's correct.
Greetings,
Rafael
Signature · 2 lines
You never change things by fighting the existing reality. R. Buckminster Fuller
Quoted 3 lines · Nigel Cunningham
Switch from bitmaps to using extents to record what swap is allocated; they make more efficient use of memory, particularly where the allocated storage is small and the swap space is large.
As I said before, I like the overall idea, but I have a bunch of comments.
Quoted 34 lines
This is also part of the ground work for implementing support for supporting multiple swap devices.
Signed-off-by Nigel Cunningham <[email protected]>kernel/power/Makefile +1
-1@@ -5,6 +5,6 @@ endif obj-y := main.o process.o console.o obj-$(CONFIG_PM_LEGACY) += pm.o -obj-$(CONFIG_SOFTWARE_SUSPEND) += swsusp.o disk.o snapshot.o swap.o user.o +obj-$(CONFIG_SOFTWARE_SUSPEND) += swsusp.o disk.o snapshot.o swap.o user.o extent.o obj-$(CONFIG_MAGIC_SYSRQ) += poweroff.okernel/power/extent.c new file +11
-0@@ -0,0 +1,119 @@ +/* +* kernel/power/extent.c +* +* Copyright (C) 2003-2006 Nigel Cunningham <[email protected]> +* Copyright (C) 2006 Red Hat, inc. +* +* Distributed under GPLv2. +* +* These functions encapsulate the manipulation of storage metadata. +*/ +
kernel/power/extent.c line 21
Quoted 10 lines
kernel/power/extent.c new file +10
-0+#include <linux/suspend.h> +#include "extent.h" + +/* suspend_get_extent +* +* Returns a free extent. May fail, returning NULL instead. +*/ +static struct extent *suspend_get_extent (void ) +{ +struct extent *result;
I'd call the type 'struct suspend_extent', for clarity.
kernel/power/extent.c line 24
Quoted 3 lines
kernel/power/extent.c new file +3
-0+ +if (!(result =kmalloc (sizeof (struct extent ),GFP_ATOMIC ))) +return NULL ;
if you use kzalloc() here, the initializations below won't be necessary and the function will reduce to a one-liner (in which case it can be inlined).
kernel/power/extent.c line 36
Quoted 12 lines
kernel/power/extent.c new file +12
-0+ + result->minimum = result->maximum =0 ; + result->next =NULL ; + +return result; +} + +/* suspend_put_extent_chain. +* +* Frees a whole chain of extents. +*/ +void suspend_put_extent_chain (struct extent_chain *chain)
I'd call it suspend_free_all_extents().
kernel/power/extent.c line 49
Quoted 13 lines
kernel/power/extent.c new file +13
-0+{ +struct extent *this; + + this = chain->first; + +while (this) { +struct extent *next = this->next; +kfree (this); + chain->num_extents--; + this = next; + } + +BUG_ON (chain->num_extents);
I'd drop this BUG_ON(). Once the code has been debugged, it's no longer of any use.
kernel/power/extent.c line 50
Quoted 1 line
kernel/power/extent.c new file +1
-0+ chain->first = chain->last_touched =NULL ;
This is against the coding style AFAICT. Please do
chain->first = NULL;chain->last_touched = NULL;
kernel/power/extent.c line 60
Quoted 10 lines
kernel/power/extent.c new file +10
-0+ chain->size =0 ; +} + +/* +* suspend_add_to_extent_chain +* +* Add an extent to an existing chain. +*/ +int suspend_add_to_extent_chain (struct extent_chain *chain, +unsigned long minimum,unsigned long maximum)
I'd use shorter names for these arguments, like 'start', 'end'.
kernel/power/extent.c line 62
Quoted 2 lines
kernel/power/extent.c new file +2
-0+{ +struct extent *new_extent =NULL , *start_at;
The names are not the best here too, IMHO. I'd use something like *new_ext, *cur_ext.
kernel/power/extent.c line 70
Quoted 8 lines
kernel/power/extent.c new file +8
-0+ +/* Find the right place in the chain */ + start_at = (chain->last_touched && + (chain->last_touched->minimum < minimum)) ? + chain->last_touched :NULL ; + +if (!start_at && chain->first && chain->first->minimum < minimum) + start_at = chain->first;
The above two statements can be simplified, like
cur_ext = NULL;
if (chain->last_touched && chain->last_touched->minimum < start)
cur_ext = chain->last_touched; else if (chain->first && chain->first->minimum < start) cur_ext = chain->first;
kernel/power/extent.c line 73
Quoted 3 lines
kernel/power/extent.c new file +3
-0+ +while (start_at && start_at->next && start_at->next->minimum < minimum) + start_at = start_at->next;
You don't need to check if start_at is nonzero in every step. It's sufficient to check this once at the beginning.
Moreover, the below is also only executed if start_at is nonzero, so you can put it under one if () along with the above loop, like this:
if (cur_ext) {
while (cur_ext->next && cur_ext->next->minimum < start)
cur_ext = cur_ext->next;
if (cur_ext-> maximum == (start - 1)) {
struct suspend_extent *next_ext;
cur_ext->maximum = end;
next_ext = cur_ext->next;
if (next_ext && cur_ext->maximum == next_ext->minimum - 1) {
cur_ext->maximum = next_ext->maximum;
cur_ext->next = next_ext->next;
kfree(next_ext);
chain->num_extents--;
}etc.
Quoted 14 lines
kernel/power/extent.c new file +14
-0+ +if (start_at && start_at->maximum == (minimum -1 )) { + start_at->maximum = maximum; + +/* Merge with the following one? */ +if (start_at->next && + start_at->maximum +1 == start_at->next->minimum) { +struct extent *to_free = start_at->next; + start_at->maximum = start_at->next->maximum; + start_at->next = start_at->next->next; + chain->num_extents--; +kfree (to_free); + } +
kernel/power/extent.c line 97
Quoted 10 lines
kernel/power/extent.c new file +10
-0+ chain->last_touched = start_at; + chain->size+= (maximum - minimum +1 ); + +return 0 ; + } + + new_extent =suspend_get_extent (); +if (!new_extent) { +printk ("Error unable to append a new extent to the chain.\n" ); +return 2 ;
return -ENOMEM;
kernel/power/extent.c line 104
Quoted 7 lines
kernel/power/extent.c new file +7
-0+ } + + chain->num_extents++; + chain->size+= (maximum - minimum +1 ); + new_extent->minimum = minimum; + new_extent->maximum = maximum; + new_extent->next =NULL ;
The last one won't be necessary if you use kzalloc() to allocate extents.
kernel/power/extent.c line 111
Quoted 7 lines
kernel/power/extent.c new file +7
-0+ + chain->last_touched = new_extent; + +if (start_at) { +struct extent *next = start_at->next; + start_at->next = new_extent; + new_extent->next = next;
*next is unnecessary here. You can do it like this:
new_ext->next = cur_ext->next;cur_ext->next = new_ext;
because new_ext->next is initially NULL.
Quoted 23 lines
kernel/power/extent.c new file +8
-0+ }else { +if (chain->first) + new_extent->next = chain->first; + chain->first = new_extent; + } + +return 0 ; +}kernel/power/extent.h new file +9
-0@@ -0,0 +1,50 @@ +/* +* kernel/power/extent.h +* +* Copyright (C) 2004-2006 Nigel Cunningham <[email protected]> +* Copyright (C) 2006 Red Hat, inc. +* +* This file is released under the GPLv2. +* +* It contains declarations related to extents. Extents are
kernel/power/extent.h line 19
Quoted 10 lines
kernel/power/extent.h new file +10
-0+* suspend's method of storing some of the metadata for the image. +* See extent.c for more info. +* +*/ + +#ifndef EXTENT_H +#define EXTENT_H + +struct extent { + unsigned long minimum, maximum;
Well, I'd use shorter names, but whatever.
Quoted 10 lines
kernel/power/extent.h new file +10
-0+struct extent *next; +}; + +struct extent_chain { +int size;/* size of the chain ie sum (max-min+1) */ +int num_extents; +struct extent *first, *last_touched; +}; + +/* Simplify iterating through all the values in an extent chain */
kernel/power/extent.h line 39
Quoted 10 lines
kernel/power/extent.h new file +10
-0+#define suspend_extent_for_each (extent_chain, extentpointer, value) \ +if ((extent_chain)->first) \ + for ((extentpointer) = (extent_chain)->first, (value) = \ + (extentpointer)->minimum; \ + ((extentpointer) && ((extentpointer)->next || (value) <= \ + (extentpointer)->maximum)); \ + (((value) == (extentpointer)->maximum) ? \ + ((extentpointer) = (extentpointer)->next, (value) = \ + ((extentpointer) ? (extentpointer)->minimum : 0)) : \ + (value)++))
This macro doesn't look very nice and is used only once, so I think you can drop it and just write the loop where it belongs.
kernel/power/extent.h line 49
Quoted 10 lines
kernel/power/extent.h new file +10
-0+ +void suspend_put_extent_chain (struct extent_chain *chain); +int suspend_add_to_extent_chain (struct extent_chain *chain, +unsigned long minimum,unsigned long maximum); + +/* swap_entry_to_extent_val & extent_val_to_swap_entry: +* We are putting offset in the low bits so consecutive swap entries +* make consecutive extent values */ +#define swap_entry_to_extent_val (swp_entry) (swp_entry.val) +#define extent_val_to_swap_entry (val) (swp_entry_t) { (val) }
These two macros are also used only once each. I'd just use the values directly.
kernel/power/extent.h line 50
Quoted 1 line
kernel/power/extent.h new file +1
-0+#endif
That's all. :-)
Greetings,
Rafael
Signature · 2 lines
You never change things by fighting the existing reality. R. Buckminster Fuller
Quoted 6 lines · Nigel Cunningham
Switch from bitmaps to using extents to record what swap is allocated; they make more efficient use of memory, particularly where the allocated storage is small and the swap space is large.
This is also part of the ground work for implementing support for supporting multiple swap devices.
In addition to the very useful comments from Rafael there's some observations of my own:
- there's an awful lot of opencoded list manipulation, any chance you could use list.h instead?
- what unit are the extent values in? The usage of unsigned long rings warning bells for me, shouldn't this be something like pgoff_t or sector_t depending on what you describe with it?
Quoted 8 lines · Christoph Hellwig
Quoted 6 lines · Nigel Cunningham
Switch from bitmaps to using extents to record what swap is allocated; they make more efficient use of memory, particularly where the allocated storage is small and the swap space is large.
This is also part of the ground work for implementing support for supporting multiple swap devices.
Quoted 8 lines
In addition to the very useful comments from Rafael there's some observations of my own:
- there's an awful lot of opencoded list manipulation, any chance you could use
list.hinstead?
- what unit are the extent values in? The usage of unsigned long rings warning bells for me, shouldn't this be something likepgoff_torsector_tdepending on what you describe with it?
These are swap offsets as returned by swp_offset().
Hi!
Quoted 6 lines
Quoted 3 lines
Switch from bitmaps to using extents to record what swap is allocated; they make more efficient use of memory, particularly where the allocated storage is small and the swap space is large.
As I said before, I like the overall idea, but I have a bunch of comments.
Okay, if Rafael likes it... lets take a look.
First... what is the _worst case_ overhead? AFAICT extents are very good at the best case, but tend to suck for the worst case...?
Quoted 7 lines
kernel/power/extent.c line 18
Quoted 7 lines
kernel/power/extent.c new file +7
-0+#include <linux/suspend.h> +#include "extent.h" + +/* suspend_get_extent +* +* Returns a free extent. May fail, returning NULL instead. +*/
Your comments are nice, and quite close to linuxdoc... Can we make them proper linuxdoc?
Quoted 7 lines
kernel/power/extent.c line 36
Quoted 5 lines
kernel/power/extent.c new file +5
-0+/* suspend_put_extent_chain. +* +* Frees a whole chain of extents. +*/ +void suspend_put_extent_chain (struct extent_chain *chain)I'd call it
suspend_free_all_extents().
This is actually important. As it does undocditional free(), it may not be called "put".
Quoted 7 lines
kernel/power/extent.h line 19
Quoted 5 lines
kernel/power/extent.h new file +5
-0+#ifndef EXTENT_H +#define EXTENT_H + +struct extent { + unsigned long minimum, maximum;Well, I'd use shorter names, but whatever.
Actually, minimum and
maximum look too similar. start/end are really better names.
Pavel
Signature · 2 lines
(english) http://www.livejournal.com/~pavelmachek (cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html
Quoted 6 lines · Pavel Machek
Hi!
Quoted 4 lines
Quoted 3 lines
Switch from bitmaps to using extents to record what swap is allocated; they make more efficient use of memory, particularly where the allocated storage is small and the swap space is large.
Quoted 7 lines
Quoted 2 lines
As I said before, I like the overall idea, but I have a bunch of comments.
Okay, if Rafael likes it... lets take a look.
First... what is the
_worstcase_overhead? AFAICT extents are very good at the best case, but tend to suck for the worst case...?
I think we'll usually be close to the best case, as we tend to allocate large consecutive blocks of swap space.
Hi.
Quoted 5 lines · Christoph Hellwig
Quoted 4 lines · Nigel Cunningham
Switch from bitmaps to using extents to record what swap is allocated; they make more efficient use of memory, particularly where the allocated storage is small and the swap space is large.
Quoted 8 lines
Quoted 2 lines
This is also part of the ground work for implementing support for supporting multiple swap devices.
In addition to the very useful comments from Rafael there's some observations of my own:
- there's an awful lot of opencoded list manipulation, any chance you could use
list.hinstead?
IIRC, I avoided list.h because I only wanted a singly linked list (it never gets traversed backwards). List.h looks to me like all doubly linked lists. Do you know if there are any other singly linked list implementations I could piggy-back?
That said, since there's normally not that many extents, I could switch quite easily and it wouldn't normally waste much memory.
Quoted 3 lines
- what unit are the extent values in? The usage of unsigned long rings warning bells for me, shouldn't this be something like
pgoff_torsector_tdepending on what you describe with it?
For this use, they're swap extents. For another use I have in suspend2, they're sector_t >> block_device_size. That's why I picked ul; something generic in what's supposed to be a generic implementation.
Thanks for the comments.
Nigel
Hi.
Quoted 6 lines · Rafael J. Wysocki
Quoted 3 lines · Nigel Cunningham
Switch from bitmaps to using extents to record what swap is allocated; they make more efficient use of memory, particularly where the allocated storage is small and the swap space is large.
As I said before, I like the overall idea, but I have a bunch of comments.
Thanks for them. Just a quick reply for the moment to say they're appreciated and I will revise accordingly.
I should also mention that this isn't the only use of these functions in Suspend2. There I also use extents to record the blocks to which the image will be written. I hope to submit modifications to swsusp to do that too in the near future.
Quoted 6 lines
Quoted 6 lines
kernel/power/extent.h new file +6
-0+/* Simplify iterating through all the values in an extent chain */ +#define suspend_extent_for_each (extent_chain, extentpointer, value) \ +if ((extent_chain)->first) \ + for ((extentpointer) = (extent_chain)->first, (value) = \ + (extentpointer)->minimum; \ + ((extentpointer) && ((extentpointer)->next || (value) <= \
Quoted 8 lines
kernel/power/extent.h line 39
Quoted 5 lines
kernel/power/extent.h new file +5
-0+ (extentpointer)->maximum)); \ + (((value) == (extentpointer)->maximum) ? \ + ((extentpointer) = (extentpointer)->next, (value) = \ + ((extentpointer) ? (extentpointer)->minimum :0 )) : \ + (value)++))This macro doesn't look very nice and is used only once, so I think you can drop it and just write the loop where it belongs.
With the modifications I mentioned just above, this would also be used for getting the blocks which match each swap extent. I can remove the macro, but just want to make you aware that it does serve a purpose, you're just not seeing it fully yet.
Quoted 5 lines
Quoted 5 lines
kernel/power/extent.h new file +5
-0+ +void suspend_put_extent_chain (struct extent_chain *chain); +int suspend_add_to_extent_chain (struct extent_chain *chain, +unsigned long minimum,unsigned long maximum); +
Quoted 8 lines
kernel/power/extent.h line 49
Quoted 5 lines
kernel/power/extent.h new file +5
-0+/* swap_entry_to_extent_val & extent_val_to_swap_entry: +* We are putting offset in the low bits so consecutive swap entries +* make consecutive extent values */ +#define swap_entry_to_extent_val (swp_entry) (swp_entry.val) +#define extent_val_to_swap_entry (val) (swp_entry_t) { (val) }These two macros are also used only once each. I'd just use the values directly.
Ok. Thanks. I think they're a leftover from 2.4 support :)
Nigel
Hi.
Quoted 6 lines · Pavel Machek
Hi!
Quoted 4 lines
Quoted 3 lines
Switch from bitmaps to using extents to record what swap is allocated; they make more efficient use of memory, particularly where the allocated storage is small and the swap space is large.
Quoted 7 lines
Quoted 2 lines
As I said before, I like the overall idea, but I have a bunch of comments.
Okay, if Rafael likes it... lets take a look.
First... what is the
_worstcase_overhead? AFAICT extents are very good at the best case, but tend to suck for the worst case...?
That's right. In using this, we're relying on the fact that the swap allocator tries to act sensibly. I've only seen worse case performance when a user had two swap devices with the same priority (striped), but that was a bug. :)
Quoted 10 lines
Quoted 7 lines
kernel/power/extent.c line 18
Quoted 7 lines
kernel/power/extent.c new file +7
-0+#include <linux/suspend.h> +#include "extent.h" + +/* suspend_get_extent +* +* Returns a free extent. May fail, returning NULL instead. +*/ Your comments are nice, and quite close to linuxdoc... Can we make them proper linuxdoc?
Ok.
Quoted 10 lines
Quoted 7 lines
kernel/power/extent.c line 36
Quoted 5 lines
kernel/power/extent.c new file +5
-0+/* suspend_put_extent_chain. +* +* Frees a whole chain of extents. +*/ +void suspend_put_extent_chain (struct extent_chain *chain)I'd call it
suspend_free_all_extents().This is actually important. As it does undocditional
free(), it may not be called "put".
Ok.
Quoted 10 lines
Quoted 7 lines
kernel/power/extent.h line 19
Quoted 5 lines
kernel/power/extent.h new file +5
-0+#ifndef EXTENT_H +#define EXTENT_H + +struct extent { + unsigned long minimum, maximum;Well, I'd use shorter names, but whatever.
Actually, minimum and
maximum look too similar. start/end are really better names.
Ok.
Thanks!
Nigel
Hi!
Quoted 9 lines
Quoted 9 lines
Quoted 6 lines
Quoted 3 lines
Switch from bitmaps to using extents to record what swap is allocated; they make more efficient use of memory, particularly where the allocated storage is small and the swap space is large.
As I said before, I like the overall idea, but I have a bunch of comments.
Okay, if Rafael likes it... lets take a look.
Quoted 7 lines
Quoted 2 lines
First... what is the
_worstcase_overhead? AFAICT extents are very good at the best case, but tend to suck for the worst case...?That's right. In using this, we're relying on the fact that the swap allocator tries to act sensibly. I've only seen worse case performance when a user had two swap devices with the same priority (striped), but that was a bug. :)
Ok, but if the allocator somehow manages to stripe between two swap devices, what happens?
IIRC original code was something like .1% overhead (8bytes per 4K, or something?), bitmaps should be even better. If it is 1% in worst case, that's probably okay, but it would be bad if it had overhead bigger than 10times original code (worst case).
Pavel
Signature · 2 lines
(english) http://www.livejournal.com/~pavelmachek (cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html
Hi.
Quoted 19 lines · Pavel Machek
Hi!
Quoted 9 lines
Quoted 9 lines
Quoted 6 lines
Quoted 3 lines
Switch from bitmaps to using extents to record what swap is allocated; they make more efficient use of memory, particularly where the allocated storage is small and the swap space is large.
As I said before, I like the overall idea, but I have a bunch of comments.
Okay, if Rafael likes it... lets take a look.
Quoted 7 lines
Quoted 2 lines
First... what is the
_worstcase_overhead? AFAICT extents are very good at the best case, but tend to suck for the worst case...?That's right. In using this, we're relying on the fact that the swap allocator tries to act sensibly. I've only seen worse case performance when a user had two swap devices with the same priority (striped), but that was a bug. :)
Quoted 7 lines
Ok, but if the allocator somehow manages to stripe between two swap devices, what happens?
IIRC original code was something like .1% overhead (8bytes per 4K, or something?), bitmaps should be even better. If it is 1% in worst case, that's probably okay, but it would be bad if it had overhead bigger than 10times original code (worst case).
With the code I have in Suspend2 (which is what I'm working towards), the value includes the swap_type, so there's no overlap. Assuming the swap allocator does it's normal thing and swap allocated is contiguous, you'll probably end up with two extents: one containing the swap allocated on the first device, and the other containing the swap allocated on the second device. So (with the current version), striping would use 6 * sizeof(unsigned long) instead of 3 * sizeof(unsigned long).
Regards,
Nigel
Hi,
Quoted 8 lines · Nigel Cunningham
Hi.
Quoted 5 lines · Rafael J. Wysocki
Quoted 3 lines · Nigel Cunningham
Switch from bitmaps to using extents to record what swap is allocated; they make more efficient use of memory, particularly where the allocated storage is small and the swap space is large.
Quoted 7 lines
Quoted 1 line
As I said before, I like the overall idea, but I have a bunch of comments.
Thanks for them. Just a quick reply for the moment to say they're appreciated and I will revise accordingly.
I should also mention that this isn't the only use of these functions in Suspend2.
Could we please focus on things that are on the table _now_?. You are submitting the patch aganist the current code and I can only review it in this context. I can't say if I like your _future_ patches at this moment! :-)
Quoted 19 lines
There I also use extents to record the blocks to which the image will be written. I hope to submit modifications to swsusp to do that too in the near future.
Quoted 6 lines
Quoted 6 lines
kernel/power/extent.h new file +6
-0+/* Simplify iterating through all the values in an extent chain */ +#define suspend_extent_for_each (extent_chain, extentpointer, value) \ +if ((extent_chain)->first) \ + for ((extentpointer) = (extent_chain)->first, (value) = \ + (extentpointer)->minimum; \ + ((extentpointer) && ((extentpointer)->next || (value) <= \Quoted 8 lines
kernel/power/extent.h line 39
Quoted 5 lines
kernel/power/extent.h new file +5
-0+ (extentpointer)->maximum)); \ + (((value) == (extentpointer)->maximum) ? \ + ((extentpointer) = (extentpointer)->next, (value) = \ + ((extentpointer) ? (extentpointer)->minimum :0 )) : \ + (value)++))This macro doesn't look very nice and is used only once, so I think you can drop it and just write the loop where it belongs.
Quoted 4 lines
With the modifications I mentioned just above, this would also be used for getting the blocks which match each swap extent. I can remove the macro, but just want to make you aware that it does serve a purpose, you're just not seeing it fully yet.
Can we just assume there are no other patches and proceed under this assumption?
Could you please remove the macro for now? You can introduce it with the other patches when you submit them (if it's still needed at that time).
Greetings,
Rafael
Signature · 2 lines
You never change things by fighting the existing reality. R. Buckminster Fuller
Quoted 7 lines · Nigel Cunningham
IIRC, I avoided
list.hbecause I only wanted a singly linked list (it never gets traversed backwards).List.hlooks to me like all doubly linked lists. Do you know if there are any other singly linked list implementations I could piggy-back?That said, since there's normally not that many extents, I could switch quite easily and it wouldn't normally waste much memory.
If the overhead doesn't matter for you (and I doubt it does) I'd say just
use list.h. Reusing existing code that doesn't need to be debugged and
is idiomatically readable to everyone is very helpfull.
Hi.
Quoted 6 lines · Christoph Hellwig
Quoted 5 lines · Nigel Cunningham
IIRC, I avoided
list.hbecause I only wanted a singly linked list (it never gets traversed backwards).List.hlooks to me like all doubly linked lists. Do you know if there are any other singly linked list implementations I could piggy-back?
Quoted 6 lines
Quoted 2 lines
That said, since there's normally not that many extents, I could switch quite easily and it wouldn't normally waste much memory.
If the overhead doesn't matter for you (and I doubt it does) I'd say just
uselist.h. Reusing existing code that doesn't need to be debugged and
is idiomatically readable to everyone is very helpfull.
Ok.
Regards,
Nigel
Hi.
Quoted 16 lines · Rafael J. Wysocki
Hi,
Quoted 13 lines · Nigel Cunningham
Hi.
Quoted 6 lines · Rafael J. Wysocki
Quoted 3 lines · Nigel Cunningham
Switch from bitmaps to using extents to record what swap is allocated; they make more efficient use of memory, particularly where the allocated storage is small and the swap space is large.
As I said before, I like the overall idea, but I have a bunch of comments.
Thanks for them. Just a quick reply for the moment to say they're appreciated and I will revise accordingly.
Quoted 6 lines
Quoted 2 lines
I should also mention that this isn't the only use of these functions in Suspend2.
Could we please focus on things that are on the table _now_?. You are submitting the patch aganist the current code and I can only review it in this context. I can't say if I like your _future_ patches at this moment! :-)
I understand that, but some things won't make sense or seem as useful if I don't give you the extra information.
Quoted 24 lines
Quoted 19 lines
There I also use extents to record the blocks to which the image will be written. I hope to submit modifications to swsusp to do that too in the near future.
Quoted 6 lines
Quoted 6 lines
kernel/power/extent.h new file +6
-0+/* Simplify iterating through all the values in an extent chain */ +#define suspend_extent_for_each (extent_chain, extentpointer, value) \ +if ((extent_chain)->first) \ + for ((extentpointer) = (extent_chain)->first, (value) = \ + (extentpointer)->minimum; \ + ((extentpointer) && ((extentpointer)->next || (value) <= \Quoted 8 lines
kernel/power/extent.h line 39
Quoted 5 lines
kernel/power/extent.h new file +5
-0+ (extentpointer)->maximum)); \ + (((value) == (extentpointer)->maximum) ? \ + ((extentpointer) = (extentpointer)->next, (value) = \ + ((extentpointer) ? (extentpointer)->minimum :0 )) : \ + (value)++))This macro doesn't look very nice and is used only once, so I think you can drop it and just write the loop where it belongs.
Quoted 4 lines
With the modifications I mentioned just above, this would also be used for getting the blocks which match each swap extent. I can remove the macro, but just want to make you aware that it does serve a purpose, you're just not seeing it fully yet.
Quoted 5 lines
Can we just assume there are no other patches and proceed under this assumption?
Could you please remove the macro for now? You can introduce it with the other patches when you submit them (if it's still needed at that time).
Ok.
Nigel
Hi!
Quoted 13 lines
Quoted 5 lines
Quoted 4 lines
That's right. In using this, we're relying on the fact that the swap allocator tries to act sensibly. I've only seen worse case performance when a user had two swap devices with the same priority (striped), but that was a bug. :)
Quoted 7 lines
Ok, but if the allocator somehow manages to stripe between two swap devices, what happens?
IIRC original code was something like .1% overhead (8bytes per 4K, or something?), bitmaps should be even better. If it is 1% in worst case, that's probably okay, but it would be bad if it had overhead bigger than 10times original code (worst case).
Quoted 8 lines
With the code I have in Suspend2 (which is what I'm working towards), the value includes the
swap_type, so there's no overlap. Assuming the swap allocator does it's normal thing and swap allocated is contiguous, you'll probably end up with two extents: one containing the swap allocated on the first device, and the other containing the swap allocated on the second device. So (with the current version), striping would use 6 * sizeof(unsigned long) instead of 3 * sizeof(unsigned long).
And now, can you do same computation assuming the swap allocator goes completely crazy, and free space is in 1-page chunks?
In particular, how much swap space can we have before we run out of low memory? What is the overhead compared to bitmaps?
Pavel
Signature · 2 lines
(english) http://www.livejournal.com/~pavelmachek (cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html
Hi.
Quoted 24 lines · Pavel Machek
Hi!
Quoted 13 lines
Quoted 5 lines
Quoted 4 lines
That's right. In using this, we're relying on the fact that the swap allocator tries to act sensibly. I've only seen worse case performance when a user had two swap devices with the same priority (striped), but that was a bug. :)
Quoted 7 lines
Ok, but if the allocator somehow manages to stripe between two swap devices, what happens?
IIRC original code was something like .1% overhead (8bytes per 4K, or something?), bitmaps should be even better. If it is 1% in worst case, that's probably okay, but it would be bad if it had overhead bigger than 10times original code (worst case).
Quoted 8 lines
With the code I have in Suspend2 (which is what I'm working towards), the value includes the
swap_type, so there's no overlap. Assuming the swap allocator does it's normal thing and swap allocated is contiguous, you'll probably end up with two extents: one containing the swap allocated on the first device, and the other containing the swap allocated on the second device. So (with the current version), striping would use 6 * sizeof(unsigned long) instead of 3 * sizeof(unsigned long).
Quoted 2 lines
And now, can you do same computation assuming the swap allocator goes completely crazy, and free space is in 1-page chunks?
The worst case is 3 * sizeof(unsigned long) *number_of_swap_extents_allocated bytes.
Quoted 2 lines
In particular, how much swap space can we have before we run out of low memory? What is the overhead compared to bitmaps?
That depends on a lot of things: the size of swap space, the amount of low memory available to begin with and so on.
I would simply say that
1) the likelihood of the worst case is extremely low, particularly in an age where swapspace is generally useless except for in suspending to disk. If it was higher, your question would be much more poignant;
2) if the worst case happens, we should handle it properly, backing out, freeing whatever we've allocated and returning control to the user, just as we should if allocating a bitmap were to fail.
Regards,
Nigel
Hi!
Quoted 9 lines
Quoted 9 lines
Quoted 8 lines
With the code I have in Suspend2 (which is what I'm working towards), the value includes the
swap_type, so there's no overlap. Assuming the swap allocator does it's normal thing and swap allocated is contiguous, you'll probably end up with two extents: one containing the swap allocated on the first device, and the other containing the swap allocated on the second device. So (with the current version), striping would use 6 * sizeof(unsigned long) instead of 3 * sizeof(unsigned long).
Quoted 5 lines
Quoted 2 lines
And now, can you do same computation assuming the swap allocator goes completely crazy, and free space is in 1-page chunks?
The worst case is 3 * sizeof(unsigned long) *
number_of_swap_extents_allocatedbytes.
Okay, so if we got 4GB of swap space, thats 1MB swap pages, worst case is you have one extent per page, on x86-64 that's 24MB. +kmalloc overhead, I assume?
And you do linear walks over those extents, leading to O(n^2) algorithm, no? That has bitten us before...
Pavel
Signature · 2 lines
(english) http://www.livejournal.com/~pavelmachek (cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html
Hi.
Quoted 14 lines · Pavel Machek
Hi!
Quoted 12 lines
Quoted 11 lines
Quoted 8 lines
With the code I have in Suspend2 (which is what I'm working towards), the value includes the
swap_type, so there's no overlap. Assuming the swap allocator does it's normal thing and swap allocated is contiguous, you'll probably end up with two extents: one containing the swap allocated on the first device, and the other containing the swap allocated on the second device. So (with the current version), striping would use 6 * sizeof(unsigned long) instead of 3 * sizeof(unsigned long).And now, can you do same computation assuming the swap allocator goes completely crazy, and free space is in 1-page chunks?
Quoted 6 lines
Quoted 2 lines
The worst case is 3 * sizeof(unsigned long) *
number_of_swap_extents_allocatedbytes.Okay, so if we got 4GB of swap space, thats 1MB swap pages, worst case is you have one extent per page, on x86-64 that's 24MB. +kmalloc overhead, I assume?
Sounds right.
Quoted 2 lines
And you do linear walks over those extents, leading to O(n^2) algorithm, no? That has bitten us before...
We start from where we last added an extent on the chain by default.
You're not going to respond to the other bit of my reply? I was beginning to think you were being more reasonable this time. Oh well.
Regards,
Nigel
Hi!
Quoted 11 lines
Quoted 9 lines
Quoted 5 lines
Quoted 2 lines
And now, can you do same computation assuming the swap allocator goes completely crazy, and free space is in 1-page chunks?
The worst case is 3 * sizeof(unsigned long) *
number_of_swap_extents_allocatedbytes.Okay, so if we got 4GB of swap space, thats 1MB swap pages, worst case is you have one extent per page, on x86-64 that's 24MB. +kmalloc overhead, I assume?
Sounds right.
Ok, 24-50MB per 4GB of swap space is not _that_ bad...
Quoted 4 lines
Quoted 2 lines
And you do linear walks over those extents, leading to O(n^2) algorithm, no? That has bitten us before...
We start from where we last added an extent on the chain by default.
...but linear search through 24MB _is_ going to hurt.
Quoted 2 lines
You're not going to respond to the other bit of my reply? I was beginning to think you were being more reasonable this time. Oh well.
Rafael likes your code, and that's a big plus, but do you have to insult me?!
Pavel
Signature · 2 lines
(english) http://www.livejournal.com/~pavelmachek (cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html
Quoted 4 lines · Nigel Cunningham
IIRC, I avoided
list.hbecause I only wanted a singly linked list (it never gets traversed backwards).List.hlooks to me like all doubly linked lists. Do you know if there are any other singly linked list implementations I could piggy-back?
Look closer in list.h, more specifically at the hlist_ entries.
Signature · 1 line
Jens Axboe
Hi.
Quoted 8 lines · Pavel Machek
Hi!
Quoted 6 lines
Quoted 6 lines
Quoted 5 lines
Quoted 2 lines
And now, can you do same computation assuming the swap allocator goes completely crazy, and free space is in 1-page chunks?
The worst case is 3 * sizeof(unsigned long) *
number_of_swap_extents_allocatedbytes.
Quoted 7 lines
Quoted 5 lines
Quoted 3 lines
Okay, so if we got 4GB of swap space, thats 1MB swap pages, worst case is you have one extent per page, on x86-64 that's 24MB. +kmalloc overhead, I assume?
Sounds right.
Ok, 24-50MB per 4GB of swap space is not _that_ bad...
Other way round: 12MB for x86, 24 for x86_64 is the worst case. Actually, come to think of it, that would be for 8GB of swap space. The worst case would require every page of swap to be alternately free and allocated, so for 4GB you'd only have 2GB of swap allocated = 1/2 the number of extents and half the memory requirements.
Quoted 6 lines
Quoted 4 lines
Quoted 2 lines
And you do linear walks over those extents, leading to O(n^2) algorithm, no? That has bitten us before...
We start from where we last added an extent on the chain by default.
...but linear search through 24MB _is_ going to hurt.
If we did one, yes it would. But this will be O(1) since we start at the last value, and get_swap_page goes through the space sequentially.
Quoted 5 lines
Quoted 2 lines
You're not going to respond to the other bit of my reply? I was beginning to think you were being more reasonable this time. Oh well.
Rafael likes your code, and that's a big plus, but do you have to insult me?!
Pavel, I never seek to insult you and I'm sorry that you felt insulted by my comment. In this case, I was expressing frustration at the fact that you seemed to be (in my opinion anyway) being unreasonable in completely ignoring and deleting my points about the likelihood of this worse case scenario, and instead focusing on calculating the requirements for such a worse case scenario, for a machine with at least 4 times the swapspace that most machines have today. I fully agree with making things robust and considering worse case scenarios, and making sure that patches are good and useful, but you seem to treat anything that comes from me as if it's infected with the plague.
How about if we just call it quits and try to be nice to each other?
Regards,
Nigel
Quoted 7 lines · Jens Axboe
Quoted 4 lines · Nigel Cunningham
IIRC, I avoided
list.hbecause I only wanted a singly linked list (it never gets traversed backwards).List.hlooks to me like all doubly linked lists. Do you know if there are any other singly linked list implementations I could piggy-back?Look closer in
list.h, more specifically at thehlist_entries.
Thanks for the pointer. I did look at it, but unless I'm misreading, it's still doubly linked. No matter. I'll use the doubly linked list.
Regards,
Nigel
Quoted 11 lines · Nigel Cunningham
Quoted 7 lines · Jens Axboe
Quoted 4 lines · Nigel Cunningham
IIRC, I avoided
list.hbecause I only wanted a singly linked list (it never gets traversed backwards).List.hlooks to me like all doubly linked lists. Do you know if there are any other singly linked list implementations I could piggy-back?Look closer in
list.h, more specifically at thehlist_entries.Thanks for the pointer. I did look at it, but unless I'm misreading, it's still doubly linked. No matter. I'll use the doubly linked list.
It is, the head just takes up a pointer less. As hch mentioned, I doubt it matters in this case at all.
Signature · 1 line
Jens Axboe
Quoted 28 lines · Nigel Cunningham
Hi.
Quoted 8 lines · Pavel Machek
Hi!
Quoted 6 lines
Quoted 6 lines
Quoted 5 lines
Quoted 2 lines
And now, can you do same computation assuming the swap allocator goes completely crazy, and free space is in 1-page chunks?
The worst case is 3 * sizeof(unsigned long) *
number_of_swap_extents_allocatedbytes.Quoted 7 lines
Quoted 5 lines
Quoted 3 lines
Okay, so if we got 4GB of swap space, thats 1MB swap pages, worst case is you have one extent per page, on x86-64 that's 24MB. +kmalloc overhead, I assume?
Sounds right.
Ok, 24-50MB per 4GB of swap space is not _that_ bad...
Other way round: 12MB for x86, 24 for
x86_64is the worst case. Actually, come to think of it, that would be for 8GB of swap space. The worst case would require every page of swap to be alternately free and allocated, so for 4GB you'd only have 2GB of swap allocated = 1/2 the number of extents and half the memory requirements.Quoted 3 lines
Quoted 3 lines
Quoted 2 lines
And you do linear walks over those extents, leading to O(n^2) algorithm, no? That has bitten us before...
Quoted 6 lines
Quoted 3 lines
Quoted 1 line
We start from where we last added an extent on the chain by default.
...but linear search through 24MB _is_ going to hurt.
If we did one, yes it would. But this will be O(1) since we start at the last value, and
get_swap_pagegoes through the space sequentially.
No, it doesn't, AFAICT, but I don't think it matters.
The question is whether there is a chance we'll get anywhere close to the worst case and I think the answer is 'no' due to the way in which the swap allocation works.
Greetings,
Rafael
Signature · 2 lines
You never change things by fighting the existing reality. R. Buckminster Fuller
Hi!
Quoted 12 lines
Quoted 12 lines
Quoted 11 lines
Quoted 9 lines
Quoted 5 lines
Quoted 2 lines
And now, can you do same computation assuming the swap allocator goes completely crazy, and free space is in 1-page chunks?
The worst case is 3 * sizeof(unsigned long) *
number_of_swap_extents_allocatedbytes.Okay, so if we got 4GB of swap space, thats 1MB swap pages, worst case is you have one extent per page, on x86-64 that's 24MB. +kmalloc overhead, I assume?
Sounds right.
Quoted 7 lines
Quoted 1 line
Ok, 24-50MB per 4GB of swap space is not _that_ bad...
Other way round: 12MB for x86, 24 for
x86_64is the worst case. Actually, come to think of it, that would be for 8GB of swap space. The worst case would require every page of swap to be alternately free and allocated, so for 4GB you'd only have 2GB of swap allocated = 1/2 the number of extents and half the memory requirements.
Ok, I was trying to do the ballpark estimate.
Quoted 11 lines
Quoted 5 lines
Quoted 2 lines
You're not going to respond to the other bit of my reply? I was beginning to think you were being more reasonable this time. Oh well.
Rafael likes your code, and that's a big plus, but do you have to insult me?!
Pavel, I never seek to insult you and I'm sorry that you felt insulted by my comment. In this case, I was expressing frustration at the fact that you seemed to be (in my opinion anyway) being unreasonable in completely ignoring and deleting my points about the likelihood of this worse case scenario, and instead focusing on calculating the
Well, deleting the points meant I mostly agree with them. But knowing how bad worst case is is still interesting (I do not think future swap allocator may not suddenly start making lots of small holes, or something). Anyway, that patch is probably okay...
Quoted 1 line
How about if we just call it quits and try to be nice to each other?
Quits.
Pavel
Signature · 2 lines
(english) http://www.livejournal.com/~pavelmachek (cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html
Hi.
Quoted 5 lines · Christoph Hellwig
Quoted 4 lines · Nigel Cunningham
Switch from bitmaps to using extents to record what swap is allocated; they make more efficient use of memory, particularly where the allocated storage is small and the swap space is large.
Quoted 8 lines
Quoted 2 lines
This is also part of the ground work for implementing support for supporting multiple swap devices.
In addition to the very useful comments from Rafael there's some observations of my own:
- there's an awful lot of opencoded list manipulation, any chance you could use
list.hinstead?
Further to this, I gave using list.h a go. Unfortunately it doesn't look to me like it is a good idea: in adding a range, I'm comparing the new range to the maximum of one extent and the minimum of the next, so finding the minimum of the next extent becomes a lot uglier than it currently is. Currently it's just ->next->minimum, but with list.h, I'd need container_of(current->list.next)->minimum. Or am I missing something?
Regards,
Nigel
Hi.
Quoted 45 lines · Rafael J. Wysocki
Quoted 3 lines · Nigel Cunningham
Switch from bitmaps to using extents to record what swap is allocated; they make more efficient use of memory, particularly where the allocated storage is small and the swap space is large.
As I said before, I like the overall idea, but I have a bunch of comments.
Quoted 38 lines
This is also part of the ground work for implementing support for supporting multiple swap devices.
Signed-off-by Nigel Cunningham <[email protected]>kernel/power/Makefile +1
-1@@ -5,6 +5,6 @@ endif obj-y := main.o process.o console.o obj-$(CONFIG_PM_LEGACY) += pm.o -obj-$(CONFIG_SOFTWARE_SUSPEND) += swsusp.o disk.o snapshot.o swap.o user.o +obj-$(CONFIG_SOFTWARE_SUSPEND) += swsusp.o disk.o snapshot.o swap.o user.o extent.o obj-$(CONFIG_MAGIC_SYSRQ) += poweroff.okernel/power/extent.c new file +15
-0@@ -0,0 +1,119 @@ +/* +* kernel/power/extent.c +* +* Copyright (C) 2003-2006 Nigel Cunningham <[email protected]> +* Copyright (C) 2006 Red Hat, inc. +* +* Distributed under GPLv2. +* +* These functions encapsulate the manipulation of storage metadata. +*/ + +#include <linux/suspend.h> +#include "extent.h" + +/* suspend_get_extent
Quoted 8 lines
kernel/power/extent.c line 21
Quoted 6 lines
kernel/power/extent.c new file +6
-0+* +* Returns a free extent. May fail, returning NULL instead. +*/ +static struct extent *suspend_get_extent (void ) +{ +struct extent *result;I'd call the type 'struct
suspend_extent', for clarity.
Done, thanks for the suggestion.
Quoted 6 lines
kernel/power/extent.c line 24
Quoted 3 lines
kernel/power/extent.c new file +3
-0+ +if (!(result =kmalloc (sizeof (struct extent ),GFP_ATOMIC ))) +return NULL ;if you use
kzalloc()here, the initializations below won't be necessary and the function will reduce to a one-liner (in which case it can be inlined).
Done.
Quoted 6 lines
Quoted 6 lines
kernel/power/extent.c new file +6
-0+ + result->minimum = result->maximum =0 ; + result->next =NULL ; + +return result; +}
Quoted 8 lines
kernel/power/extent.c line 36
Quoted 6 lines
kernel/power/extent.c new file +6
-0+ +/* suspend_put_extent_chain. +* +* Frees a whole chain of extents. +*/ +void suspend_put_extent_chain (struct extent_chain *chain)I'd call it
suspend_free_all_extents().
Renamed as suspend_free_extent_chain (I'm thinking of future use of multiple chains for multiple swap devices).
Quoted 8 lines
Quoted 8 lines
kernel/power/extent.c new file +8
-0+{ +struct extent *this; + + this = chain->first; + +while (this) { +struct extent *next = this->next; +kfree (this);
Quoted 8 lines
kernel/power/extent.c line 49
Quoted 5 lines
kernel/power/extent.c new file +5
-0+ chain->num_extents--; + this = next; + } + +BUG_ON (chain->num_extents);I'd drop this
BUG_ON(). Once the code has been debugged, it's no longer of any use.
Done.
Quoted 6 lines
kernel/power/extent.c line 50
Quoted 1 line
kernel/power/extent.c new file +1
-0+ chain->first = chain->last_touched =NULL ;This is against the coding style AFAICT. Please do
chain->first= NULL;chain->last_touched= NULL;
Done. Didn't know that, thanks.
Quoted 4 lines
Quoted 4 lines
kernel/power/extent.c new file +4
-0+ chain->size =0 ; +} + +/*
Quoted 8 lines
kernel/power/extent.c line 60
Quoted 6 lines
kernel/power/extent.c new file +6
-0+* suspend_add_to_extent_chain +* +* Add an extent to an existing chain. +*/ +int suspend_add_to_extent_chain (struct extent_chain *chain, +unsigned long minimum,unsigned long maximum)I'd use shorter names for these arguments, like 'start', 'end'.
min & max now used.
Quoted 17 lines
kernel/power/extent.c line 62
Quoted 2 lines
kernel/power/extent.c new file +2
-0+{ +struct extent *new_extent =NULL , *start_at;The names are not the best here too, IMHO. I'd use something like
*new_ext,*cur_ext.kernel/power/extent.c line 70
Quoted 8 lines
kernel/power/extent.c new file +8
-0+ +/* Find the right place in the chain */ + start_at = (chain->last_touched && + (chain->last_touched->minimum < minimum)) ? + chain->last_touched :NULL ; + +if (!start_at && chain->first && chain->first->minimum < minimum) + start_at = chain->first;The above two statements can be simplified, like
Quoted 5 lines
cur_ext= NULL;
if (chain->last_touched&&chain->last_touched->minimum< start)cur_ext = chain->last_touched; else if (chain->first && chain->first->minimum < start) cur_ext = chain->first;
Done, ta.
Quoted 9 lines
kernel/power/extent.c line 73
Quoted 3 lines
kernel/power/extent.c new file +3
-0+ +while (start_at && start_at->next && start_at->next->minimum < minimum) + start_at = start_at->next;You don't need to check if
start_atis nonzero in every step. It's sufficient to check this once at the beginning.Moreover, the below is also only executed if
start_atis nonzero, so you can put it under one if () along with the above loop, like this:
Done, ta.
Quoted 35 lines
if (cur_ext) { while (cur_ext->next && cur_ext->next->minimum < start) cur_ext = cur_ext->next; if (cur_ext-> maximum == (start - 1)) { struct suspend_extent *next_ext; cur_ext->maximum = end; next_ext = cur_ext->next; if (next_ext && cur_ext->maximum == next_ext->minimum - 1) { cur_ext->maximum = next_ext->maximum; cur_ext->next = next_ext->next; kfree(next_ext); chain->num_extents--; }etc.
Quoted 18 lines
kernel/power/extent.c new file +18
-0+ +if (start_at && start_at->maximum == (minimum -1 )) { + start_at->maximum = maximum; + +/* Merge with the following one? */ +if (start_at->next && + start_at->maximum +1 == start_at->next->minimum) { +struct extent *to_free = start_at->next; + start_at->maximum = start_at->next->maximum; + start_at->next = start_at->next->next; + chain->num_extents--; +kfree (to_free); + } + + chain->last_touched = start_at; + chain->size+= (maximum - minimum +1 ); + +return 0 ;
Quoted 8 lines
kernel/power/extent.c line 97
Quoted 6 lines
kernel/power/extent.c new file +6
-0+ } + + new_extent =suspend_get_extent (); +if (!new_extent) { +printk ("Error unable to append a new extent to the chain.\n" ); +return 2 ;return
-ENOMEM;
Mmm. Ta. Forgotten defunct debugging.
Quoted 9 lines
kernel/power/extent.c line 104
Quoted 7 lines
kernel/power/extent.c new file +7
-0+ } + + chain->num_extents++; + chain->size+= (maximum - minimum +1 ); + new_extent->minimum = minimum; + new_extent->maximum = maximum; + new_extent->next =NULL ;The last one won't be necessary if you use
kzalloc()to allocate extents.
Ack.
Quoted 10 lines
kernel/power/extent.c line 111
Quoted 7 lines
kernel/power/extent.c new file +7
-0+ + chain->last_touched = new_extent; + +if (start_at) { +struct extent *next = start_at->next; + start_at->next = new_extent; + new_extent->next = next;*next is unnecessary here. You can do it like this:
Quoted 4 lines
new_ext->next=cur_ext->next;cur_ext->next=new_ext;because
new_ext->nextis initially NULL.
k.
Quoted 51 lines
Quoted 23 lines
kernel/power/extent.c new file +8
-0+ }else { +if (chain->first) + new_extent->next = chain->first; + chain->first = new_extent; + } + +return 0 ; +}kernel/power/extent.h new file +9
-0@@ -0,0 +1,50 @@ +/* +* kernel/power/extent.h +* +* Copyright (C) 2004-2006 Nigel Cunningham <[email protected]> +* Copyright (C) 2006 Red Hat, inc. +* +* This file is released under the GPLv2. +* +* It contains declarations related to extents. Extents are kernel/power/extent.h line 19
Quoted 10 lines
kernel/power/extent.h new file +10
-0+* suspend's method of storing some of the metadata for the image. +* See extent.c for more info. +* +*/ + +#ifndef EXTENT_H +#define EXTENT_H + +struct extent { + unsigned long minimum, maximum;Well, I'd use shorter names, but whatever.
Quoted 15 lines
kernel/power/extent.h new file +15
-0+struct extent *next; +}; + +struct extent_chain { +int size;/* size of the chain ie sum (max-min+1) */ +int num_extents; +struct extent *first, *last_touched; +}; + +/* Simplify iterating through all the values in an extent chain */ +#define suspend_extent_for_each (extent_chain, extentpointer, value) \ +if ((extent_chain)->first) \ + for ((extentpointer) = (extent_chain)->first, (value) = \ + (extentpointer)->minimum; \ + ((extentpointer) && ((extentpointer)->next || (value) <= \
Quoted 8 lines
kernel/power/extent.h line 39
Quoted 5 lines
kernel/power/extent.h new file +5
-0+ (extentpointer)->maximum)); \ + (((value) == (extentpointer)->maximum) ? \ + ((extentpointer) = (extentpointer)->next, (value) = \ + ((extentpointer) ? (extentpointer)->minimum :0 )) : \ + (value)++))This macro doesn't look very nice and is used only once, so I think you can drop it and just write the loop where it belongs.
Sort of done - expanded to two loops. 'tis more readable that way anyway.
Quoted 5 lines
Quoted 5 lines
kernel/power/extent.h new file +5
-0+ +void suspend_put_extent_chain (struct extent_chain *chain); +int suspend_add_to_extent_chain (struct extent_chain *chain, +unsigned long minimum,unsigned long maximum); +
Quoted 8 lines
kernel/power/extent.h line 49
Quoted 5 lines
kernel/power/extent.h new file +5
-0+/* swap_entry_to_extent_val & extent_val_to_swap_entry: +* We are putting offset in the low bits so consecutive swap entries +* make consecutive extent values */ +#define swap_entry_to_extent_val (swp_entry) (swp_entry.val) +#define extent_val_to_swap_entry (val) (swp_entry_t) { (val) }These two macros are also used only once each. I'd just use the values directly.
ack
Quoted 3 lines
kernel/power/extent.h line 50
Quoted 1 line
kernel/power/extent.h new file +1
-0+#endif That's all. :-)
Thanks.
Quoted 2 lines
You never change things by fighting the existing reality.
R. Buckminster Fuller
Hmm. Maybe I shouldn't bother with this then :)
Nigel
Quoted 17 lines
Hi.
Quoted 5 lines · Christoph Hellwig
Quoted 4 lines · Nigel Cunningham
Switch from bitmaps to using extents to record what swap is allocated; they make more efficient use of memory, particularly where the allocated storage is small and the swap space is large.
Quoted 8 lines
Quoted 2 lines
This is also part of the ground work for implementing support for supporting multiple swap devices.
In addition to the very useful comments from Rafael there's some observations of my own:
- there's an awful lot of opencoded list manipulation, any chance you could use
list.hinstead?
Quoted 7 lines
Further to this, I gave using
list.ha go. Unfortunately it doesn't look to me like it is a good idea: in adding a range, I'm comparing the new range to the maximum of one extent and the minimum of the next, so finding the minimum of the next extent becomes a lot uglier than it currently is. Currently it's just ->next->minimum, but withlist.h, I'd need container_of(current->list.next)->minimum. Or am I missing something?
That does not look that scary... just do it.
Pavel
Signature · 1 line
Thanks, Sharp!
Hi.
Quoted 25 lines · Pavel Machek
Quoted 17 lines
Hi.
Quoted 5 lines · Christoph Hellwig
Quoted 4 lines · Nigel Cunningham
Switch from bitmaps to using extents to record what swap is allocated; they make more efficient use of memory, particularly where the allocated storage is small and the swap space is large.
Quoted 8 lines
Quoted 2 lines
This is also part of the ground work for implementing support for supporting multiple swap devices.
In addition to the very useful comments from Rafael there's some observations of my own:
- there's an awful lot of opencoded list manipulation, any chance you could use
list.hinstead?Quoted 7 lines
Further to this, I gave using
list.ha go. Unfortunately it doesn't look to me like it is a good idea: in adding a range, I'm comparing the new range to the maximum of one extent and the minimum of the next, so finding the minimum of the next extent becomes a lot uglier than it currently is. Currently it's just ->next->minimum, but withlist.h, I'd need container_of(current->list.next)->minimum. Or am I missing something?
Quoted 1 line
That does not look that scary... just do it.
It currently makes more sense to me to stick with what I already have because it's simpler and more readable.
Regards,
Nigel