[PATCH] Use extents for recording what swap is allocated.
From: Nigel Cunningham
Date: Mon Oct 23 2006 - 00:14:42 EST
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.
Signed-off-by: Nigel Cunningham <nigel@xxxxxxxxxxxx>
diff --git a/kernel/power/Makefile b/kernel/power/Makefile
index 38725f5..d772521 100644
--- a/kernel/power/Makefile
+++ b/kernel/power/Makefile
@@ -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
diff --git a/kernel/power/extent.c b/kernel/power/extent.c
new file mode 100644
index 0000000..b769956
--- /dev/null
+++ b/kernel/power/extent.c
@@ -0,0 +1,119 @@
+/*
+ * kernel/power/extent.c
+ *
+ * Copyright (C) 2003-2006 Nigel Cunningham <nigel@xxxxxxxxxxxx>
+ * 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
+ *
+ * Returns a free extent. May fail, returning NULL instead.
+ */
+static struct extent *suspend_get_extent(void)
+{
+ struct extent *result;
+
+ if (!(result = kmalloc(sizeof(struct extent), GFP_ATOMIC)))
+ return NULL;
+
+ 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)
+{
+ 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);
+ chain->first = chain->last_touched = NULL;
+ 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)
+{
+ struct extent *new_extent = NULL, *start_at;
+
+ /* 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;
+
+ while (start_at && start_at->next && start_at->next->minimum < minimum)
+ start_at = start_at->next;
+
+ 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;
+ }
+
+ new_extent = suspend_get_extent();
+ if (!new_extent) {
+ printk("Error unable to append a new extent to the chain.\n");
+ return 2;
+ }
+
+ chain->num_extents++;
+ chain->size+= (maximum - minimum + 1);
+ new_extent->minimum = minimum;
+ new_extent->maximum = maximum;
+ new_extent->next = NULL;
+
+ chain->last_touched = new_extent;
+
+ if (start_at) {
+ struct extent *next = start_at->next;
+ start_at->next = new_extent;
+ new_extent->next = next;
+ } else {
+ if (chain->first)
+ new_extent->next = chain->first;
+ chain->first = new_extent;
+ }
+
+ return 0;
+}
diff --git a/kernel/power/extent.h b/kernel/power/extent.h
new file mode 100644
index 0000000..062b4c1
--- /dev/null
+++ b/kernel/power/extent.h
@@ -0,0 +1,50 @@
+/*
+ * kernel/power/extent.h
+ *
+ * Copyright (C) 2004-2006 Nigel Cunningham <nigel@xxxxxxxxxxxx>
+ * Copyright (C) 2006 Red Hat, inc.
+ *
+ * This file is released under the GPLv2.
+ *
+ * It contains declarations related to extents. Extents are
+ * 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;
+ 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) <= \
+ (extentpointer)->maximum)); \
+ (((value) == (extentpointer)->maximum) ? \
+ ((extentpointer) = (extentpointer)->next, (value) = \
+ ((extentpointer) ? (extentpointer)->minimum : 0)) : \
+ (value)++))
+
+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) }
+#endif
diff --git a/kernel/power/power.h b/kernel/power/power.h
index bfe999f..a78c391 100644
--- a/kernel/power/power.h
+++ b/kernel/power/power.h
@@ -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);
diff --git a/kernel/power/swap.c b/kernel/power/swap.c
index 1a3b0dd..fc713d5 100644
--- a/kernel/power/swap.c
+++ b/kernel/power/swap.c
@@ -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 s
if (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_m
if (!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;
}
diff --git a/kernel/power/swsusp.c b/kernel/power/swsusp.c
index 0b66659..aa8205c 100644
--- a/kernel/power/swsusp.c
+++ b/kernel/power/swsusp.c
@@ -51,6 +51,7 @@ #include <linux/syscalls.h>
#include <linux/highmem.h>
#include "power.h"
+#include "extent.h"
/*
* Preferred image size in bytes (tunable via /sys/power/image_size).
@@ -72,96 +73,30 @@ static inline int restore_highmem(void)
static inline unsigned int count_highmem_pages(void) { return 0; }
#endif
-/**
- * The following functions are used for tracing the allocated
- * swap pages, so that they can be freed in case of an error.
- *
- * The functions operate on a linked bitmap structure defined
- * in power.h
- */
-
-void free_bitmap(struct bitmap_page *bitmap)
+unsigned long alloc_swap_page(int swap, struct extent_chain *extents)
{
- struct bitmap_page *bp;
-
- while (bitmap) {
- bp = bitmap->next;
- free_page((unsigned long)bitmap);
- bitmap = bp;
+ swp_entry_t entry = get_swap_page_of_type(swap);
+ if (entry.val) {
+ unsigned long new_value = swap_entry_to_extent_val(entry);
+ suspend_add_to_extent_chain(extents, new_value, new_value);
}
+ return swp_offset(entry);
}
-struct bitmap_page *alloc_bitmap(unsigned int nr_bits)
+void free_all_swap_pages(int swap, struct extent_chain *extents)
{
- struct bitmap_page *bitmap, *bp;
- unsigned int n;
-
- if (!nr_bits)
- return NULL;
-
- bitmap = (struct bitmap_page *)get_zeroed_page(GFP_KERNEL);
- bp = bitmap;
- for (n = BITMAP_PAGE_BITS; n < nr_bits; n += BITMAP_PAGE_BITS) {
- bp->next = (struct bitmap_page *)get_zeroed_page(GFP_KERNEL);
- bp = bp->next;
- if (!bp) {
- free_bitmap(bitmap);
- return NULL;
+ if (extents->first) {
+ /* Free swap entries */
+ struct extent *extentpointer;
+ unsigned long extentvalue;
+ swp_entry_t entry;
+ suspend_extent_for_each(extents, extentpointer,
+ extentvalue) {
+ entry = extent_val_to_swap_entry(extentvalue);
+ swap_free(entry);
}
- }
- return bitmap;
-}
-
-static int bitmap_set(struct bitmap_page *bitmap, unsigned long bit)
-{
- unsigned int n;
- n = BITMAP_PAGE_BITS;
- while (bitmap && n <= bit) {
- n += BITMAP_PAGE_BITS;
- bitmap = bitmap->next;
- }
- if (!bitmap)
- return -EINVAL;
- n -= BITMAP_PAGE_BITS;
- bit -= n;
- n = 0;
- while (bit >= BITS_PER_CHUNK) {
- bit -= BITS_PER_CHUNK;
- n++;
- }
- bitmap->chunks[n] |= (1UL << bit);
- return 0;
-}
-
-unsigned long alloc_swap_page(int swap, struct bitmap_page *bitmap)
-{
- unsigned long offset;
-
- offset = swp_offset(get_swap_page_of_type(swap));
- if (offset) {
- if (bitmap_set(bitmap, offset)) {
- swap_free(swp_entry(swap, offset));
- offset = 0;
- }
- }
- return offset;
-}
-
-void free_all_swap_pages(int swap, struct bitmap_page *bitmap)
-{
- unsigned int bit, n;
- unsigned long test;
-
- bit = 0;
- while (bitmap) {
- for (n = 0; n < BITMAP_PAGE_CHUNKS; n++)
- for (test = 1UL; test; test <<= 1) {
- if (bitmap->chunks[n] & test)
- swap_free(swp_entry(swap, bit));
- bit++;
- }
- bitmap = bitmap->next;
+ suspend_put_extent_chain(extents);
}
}
diff --git a/kernel/power/user.c b/kernel/power/user.c
index 3653b22..79aa849 100644
--- a/kernel/power/user.c
+++ b/kernel/power/user.c
@@ -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 inode
swsusp_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
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/