[PATCH] Dynamically allocated pageflags

[Nigel Cunningham <ncunningham@cyclades.com>]

Hi everyone.

This is my latest revision of the dynamically allocated pageflags patch.

The patch is useful for kernel space applications that sometimes need to flag
pages for some purpose, but don't otherwise need the retain the state. A prime
example is suspend-to-disk, which needs to flag pages as unsaveable, allocated
by suspend-to-disk and the like while it is working, but doesn't need to
retain any of this state between cycles.

Since the last revision, I have switched to using per-zone bitmaps within each
bitmap.

I know that I could still add hotplug memory support. Is there anything else
missing?

Regards,

Nigel

 include/linux/dyn_pageflags.h |   66 ++++++++
 lib/Kconfig                   |    3 
 lib/Makefile                  |    2 
 lib/dyn_pageflags.c           |  330 ++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 401 insertions(+)
diff -ruNp 3150-dynamic-pageflags.patch-old/include/linux/dyn_pageflags.h 3150-dynamic-pageflags.patch-new/include/linux/dyn_pageflags.h
--- 3150-dynamic-pageflags.patch-old/include/linux/dyn_pageflags.h	1970-01-01 10:00:00.000000000 +1000
+++ 3150-dynamic-pageflags.patch-new/include/linux/dyn_pageflags.h	2006-02-02 21:09:57.000000000 +1000
@@ -0,0 +1,66 @@
+/*
+ * include/linux/dyn_pageflags.h
+ *
+ * Copyright (C) 2004-2006 Nigel Cunningham <nigel@suspend2.net>
+ *
+ * This file is released under the GPLv2.
+ *
+ * It implements support for dynamically allocated bitmaps that are
+ * used for temporary or infrequently used pageflags, in lieu of
+ * bits in the struct page flags entry.
+ */
+
+#ifndef DYN_PAGEFLAGS_H
+#define DYN_PAGEFLAGS_H
+
+#include <linux/mm.h>
+
+typedef unsigned long *** dyn_pageflags_t;
+
+#define BITNUMBER(page) (page_to_pfn(page))
+
+#if BITS_PER_LONG == 32
+#define UL_SHIFT 5
+#else 
+#if BITS_PER_LONG == 64
+#define UL_SHIFT 6
+#else
+#error Bits per long not 32 or 64?
+#endif
+#endif
+
+#define BIT_NUM_MASK (sizeof(unsigned long) * 8 - 1)
+#define PAGE_NUM_MASK (~((1 << (PAGE_SHIFT + 3)) - 1))
+#define UL_NUM_MASK (~(BIT_NUM_MASK | PAGE_NUM_MASK))
+
+#define BITS_PER_PAGE (PAGE_SIZE << 3)
+#define PAGENUMBER(zone_offset) (zone_offset >> (PAGE_SHIFT + 3))
+#define PAGEINDEX(zone_offset) ((zone_offset & UL_NUM_MASK) >> UL_SHIFT)
+#define PAGEBIT(zone_offset) (zone_offset & BIT_NUM_MASK)
+
+#define PAGE_UL_PTR(bitmap, zone_num, zone_pfn) \
+       ((bitmap[zone_num][PAGENUMBER(zone_pfn)])+PAGEINDEX(zone_pfn))
+
+/* With the above macros defined, you can do...
+
+#define PagePageset1(page) (test_dynpageflag(&pageset1_map, page))
+#define SetPagePageset1(page) (set_dynpageflag(&pageset1_map, page))
+#define ClearPagePageset1(page) (clear_dynpageflag(&pageset1_map, page))
+*/
+
+#define BITMAP_FOR_EACH_SET(bitmap, counter) \
+	for (counter = get_next_bit_on(bitmap, -1); counter < max_pfn; \
+		counter = get_next_bit_on(bitmap, counter))
+
+extern void clear_dyn_pageflags(dyn_pageflags_t pagemap);
+extern int allocate_dyn_pageflags(dyn_pageflags_t *pagemap);
+extern int free_dyn_pageflags(dyn_pageflags_t *pagemap);
+extern int dyn_pageflags_pages_per_bitmap(void);
+extern int get_next_bit_on(dyn_pageflags_t bitmap, int counter);
+extern unsigned long *dyn_pageflags_ul_ptr(dyn_pageflags_t *bitmap,
+		struct page *pg);
+
+extern int test_dynpageflag(dyn_pageflags_t *bitmap, struct page *page);
+extern void set_dynpageflag(dyn_pageflags_t *bitmap, struct page *page);
+extern void clear_dynpageflag(dyn_pageflags_t *bitmap, struct page *page);
+#endif
diff -ruNp 3150-dynamic-pageflags.patch-old/lib/dyn_pageflags.c 3150-dynamic-pageflags.patch-new/lib/dyn_pageflags.c
--- 3150-dynamic-pageflags.patch-old/lib/dyn_pageflags.c	1970-01-01 10:00:00.000000000 +1000
+++ 3150-dynamic-pageflags.patch-new/lib/dyn_pageflags.c	2006-02-02 21:09:44.000000000 +1000
@@ -0,0 +1,330 @@
+/*
+ * lib/dyn_pageflags.c
+ *
+ * Copyright (C) 2004-2006 Nigel Cunningham <nigel@suspend2.net>
+ * 
+ * This file is released under the GPLv2.
+ *
+ * Routines for dynamically allocating and releasing bitmaps
+ * used as pseudo-pageflags.
+ *
+ * Arrays are not contiguous. The first sizeof(void *) bytes are
+ * the pointer to the next page in the bitmap. This allows us to
+ * work under low memory conditions where order 0 might be all
+ * that's available. In their original use (suspend2), it also
+ * lets us save the pages at suspend time, reload and relocate them
+ * as necessary at resume time without much effort.
+ *
+ */
+
+#include <linux/module.h>
+#include <linux/dyn_pageflags.h>
+#include <linux/bootmem.h>
+
+#define page_to_zone_offset(pg) (page_to_pfn(pg) - page_zone(pg)->zone_start_pfn)
+
+/* 
+ * num_zones
+ * 
+ * How many zones are there?
+ *
+ */
+
+static int num_zones(void)
+{
+	int result = 0;
+	struct zone *zone;
+
+	for_each_zone(zone)
+		result++;
+
+	return result;
+}
+
+/* 
+ * pages_for_zone(struct zone *zone)
+ * 
+ * How many pages do we need for a bitmap for this zone?
+ *
+ */
+
+static int pages_for_zone(struct zone *zone)
+{
+	return (zone->spanned_pages + (PAGE_SIZE << 3) - 1) >>
+			(PAGE_SHIFT + 3);
+}
+
+/*
+ * page_zone_number(struct page *page)
+ *
+ * Which zone index does the page match?
+ *
+ */
+
+static int page_zone_number(struct page *page)
+{
+	struct zone *zone, *zone_sought = page_zone(page);
+	int zone_num = 0;
+
+	for_each_zone(zone)
+		if (zone == zone_sought)
+			return zone_num;
+		else
+			zone_num++;
+
+	printk("Was looking for a zone for page %p.\n", page);
+	BUG_ON(1);
+
+	return 0;
+}
+
+/*
+ * dyn_pageflags_pages_per_bitmap
+ *
+ * Number of pages needed for a bitmap covering all zones.
+ *
+ */
+int dyn_pageflags_pages_per_bitmap(void)
+{
+	int total = 0;
+	struct zone *zone;
+
+	for_each_zone(zone)
+		total += pages_for_zone(zone);
+
+	return total;
+}
+
+/* 
+ * clear_dyn_pageflags(dyn_pageflags_t pagemap)
+ *
+ * Clear an array used to store local page flags.
+ *
+ */
+
+void clear_dyn_pageflags(dyn_pageflags_t pagemap)
+{
+	int i = 0, zone_num = 0;
+	struct zone *zone;
+	
+	BUG_ON(!pagemap);
+
+	for_each_zone(zone) {
+		for (i = 0; i < pages_for_zone(zone); i++)
+			memset((pagemap[zone_num][i]), 0, PAGE_SIZE);
+		zone_num++;
+	}
+}
+
+/* 
+ * allocate_dyn_pageflags(dyn_pageflags_t *pagemap)
+ *
+ * Allocate a bitmap for dynamic page flags.
+ *
+ */
+int allocate_dyn_pageflags(dyn_pageflags_t *pagemap)
+{
+	int i, zone_num = 0;
+	struct zone *zone;
+
+	BUG_ON(*pagemap);
+
+	*pagemap = kmalloc(sizeof(void *) * num_zones(), GFP_ATOMIC);
+
+	if (!*pagemap)
+		return -ENOMEM;
+
+	for_each_zone(zone) {
+		int zone_pages = pages_for_zone(zone);
+		(*pagemap)[zone_num] = kmalloc(sizeof(void *) * zone_pages,
+					       GFP_ATOMIC);
+
+		if (!(*pagemap)[zone_num]) {
+			kfree (*pagemap);
+			return -ENOMEM;
+		}
+
+		for (i = 0; i < zone_pages; i++) {
+			unsigned long address = get_zeroed_page(GFP_ATOMIC);
+			(*pagemap)[zone_num][i] = (unsigned long *) address;
+			if (!(*pagemap)[zone_num][i]) {
+				printk("Error. Unable to allocate memory for "
+					"dynamic pageflags.");
+				free_dyn_pageflags(pagemap);
+				return -ENOMEM;
+			}
+		}
+		zone_num++;
+	}
+
+	return 0;
+}
+
+/* 
+ * free_dyn_pageflags(dyn_pageflags_t *pagemap)
+ *
+ * Free a dynamically allocated pageflags bitmap. For Suspend2 usage, we
+ * support data being relocated from slab to pages that don't conflict
+ * with the image that will be copied back. This is the reason for the
+ * PageSlab tests below.
+ *
+ */
+void free_dyn_pageflags(dyn_pageflags_t *pagemap)
+{
+	int i = 0, zone_num = 0;
+	struct zone *zone;
+
+	if (!*pagemap)
+		return;
+	
+	for_each_zone(zone) {
+		int zone_pages = pages_for_zone(zone);
+
+		if (!((*pagemap)[zone_num]))
+			continue;
+		for (i = 0; i < zone_pages; i++)
+			if ((*pagemap)[zone_num][i])
+				free_page((unsigned long) (*pagemap)[zone_num][i]);
+	
+		if (PageSlab(virt_to_page((*pagemap)[zone_num])))
+			kfree((*pagemap)[zone_num]);
+		else
+			free_page((unsigned long) (*pagemap)[zone_num]);
+
+		zone_num++;
+	}
+
+	if (PageSlab(virt_to_page((*pagemap))))
+		kfree(*pagemap);
+	else
+		free_page((unsigned long) (*pagemap));
+
+	*pagemap = NULL;
+	return;
+}
+
+/*
+ * dyn_pageflags_ul_ptr(dyn_pageflags_t *bitmap, struct page *pg)
+ *
+ * Get a pointer to the unsigned long containing the flag in the bitmap
+ * for the given page.
+ *
+ */
+
+unsigned long *dyn_pageflags_ul_ptr(dyn_pageflags_t *bitmap, struct page *pg)
+{
+	int zone_pfn = page_to_zone_offset(pg);
+	int zone_num = page_zone_number(pg);
+	int pagenum = PAGENUMBER(zone_pfn);
+	int page_offset = PAGEINDEX(zone_pfn);
+	return ((*bitmap)[zone_num][pagenum]) + page_offset;
+}
+
+/*
+ * test_dynpageflag(dyn_pageflags_t *bitmap, struct page *page)
+ *
+ * Is the page flagged in the given bitmap?
+ *
+ */
+
+int test_dynpageflag(dyn_pageflags_t *bitmap, struct page *page)
+{
+	unsigned long *ul = dyn_pageflags_ul_ptr(bitmap, page);
+	int zone_offset = page_to_zone_offset(page);
+	int bit = PAGEBIT(zone_offset);
+	
+	return test_bit(bit, ul);
+}
+
+/*
+ * set_dynpageflag(dyn_pageflags_t *bitmap, struct page *page)
+ *
+ * Set the flag for the page in the given bitmap.
+ *
+ */
+
+void set_dynpageflag(dyn_pageflags_t *bitmap, struct page *page)
+{
+	unsigned long *ul = dyn_pageflags_ul_ptr(bitmap, page);
+	int zone_offset = page_to_zone_offset(page);
+	int bit = PAGEBIT(zone_offset);
+	set_bit(bit, ul);
+}
+
+/*
+ * clear_dynpageflags(dyn_pageflags_t *bitmap, struct page *page)
+ *
+ * Clear the flag for the page in the given bitmap.
+ *
+ */
+
+void clear_dynpageflag(dyn_pageflags_t *bitmap, struct page *page)
+{
+	unsigned long *ul = dyn_pageflags_ul_ptr(bitmap, page);
+	int zone_offset = page_to_zone_offset(page);
+	int bit = PAGEBIT(zone_offset);
+	clear_bit(bit, ul);
+}
+
+/*
+ * get_next_bit_on(dyn_pageflags_t bitmap, int counter)
+ *
+ * Given a pfn (possibly -1), find the next pfn in the bitmap that
+ * is set. If there are no more flags set, return max_pfn.
+ *
+ */
+
+int get_next_bit_on(dyn_pageflags_t bitmap, int counter)
+{
+	struct page *page;
+	struct zone *zone;
+	unsigned long *ul;
+	int zone_offset, pagebit, zone_num, first;
+
+	BUG_ON(counter == max_pfn);
+
+	first = (counter == -1);
+	
+	if (first)
+		counter = pgdat_list->node_zones->zone_start_pfn;
+
+	page = pfn_to_page(counter);
+	zone = page_zone(page);
+	zone_num = page_zone_number(page);
+
+	if (!first)
+		counter++;
+	
+	zone_offset = counter - zone->zone_start_pfn;
+
+	do {
+		if (zone_offset >= zone->spanned_pages) {
+			do {
+				zone = next_zone(zone);
+				if (!zone)
+					return max_pfn;
+				zone_num++;
+			} while(!zone->spanned_pages);
+
+			counter = zone->zone_start_pfn;
+			zone_offset = 0;
+			page = pfn_to_page(counter);
+		}
+		
+		/*
+		 * This could be optimised, but there are more
+		 * important things and the code is simple at
+		 * the moment 
+		 */
+		ul = (bitmap[zone_num][PAGENUMBER(zone_offset)]) + PAGEINDEX(zone_offset);
+		
+		pagebit = PAGEBIT(zone_offset);
+
+		counter++;
+		zone_offset++;
+		page = pfn_to_page(counter);
+	
+	} while((counter <= max_pfn) && (!test_bit(pagebit, ul)));
+	return counter - 1;
+}
+
diff -ruNp 3150-dynamic-pageflags.patch-old/lib/Kconfig 3150-dynamic-pageflags.patch-new/lib/Kconfig
--- 3150-dynamic-pageflags.patch-old/lib/Kconfig	2006-01-19 21:28:05.000000000 +1000
+++ 3150-dynamic-pageflags.patch-new/lib/Kconfig	2006-01-24 06:54:07.000000000 +1000
@@ -38,6 +38,9 @@ config LIBCRC32C
 	  require M here.  See Castagnoli93.
 	  Module will be libcrc32c.
 
+config DYN_PAGEFLAGS
+	bool
+
 #
 # compression support is select'ed if needed
 #
diff -ruNp 3150-dynamic-pageflags.patch-old/lib/Makefile 3150-dynamic-pageflags.patch-new/lib/Makefile
--- 3150-dynamic-pageflags.patch-old/lib/Makefile	2006-01-19 21:28:05.000000000 +1000
+++ 3150-dynamic-pageflags.patch-new/lib/Makefile	2006-01-24 06:54:07.000000000 +1000
@@ -28,6 +28,8 @@ ifneq ($(CONFIG_HAVE_DEC_LOCK),y)
   lib-y += dec_and_lock.o
 endif
 
+obj-$(CONFIG_DYN_PAGEFLAGS) += dyn_pageflags.o
+
 obj-$(CONFIG_CRC_CCITT)	+= crc-ccitt.o
 obj-$(CONFIG_CRC16)	+= crc16.o
 obj-$(CONFIG_CRC32)	+= crc32.o

Attachment: pgpzqUHvfTDL8.pgp
Description: PGP signature