Dynamically allocated pageflags

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
@@ -0,0 +1,66 @@
+/*
+ * include/linux/dyn_pageflags.h
+ *
+ * Copyright (C) 2004-2006 Nigel Cunningham <[email protected]>
+ *
+ * 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/Kconfig 3150-dynamic-pageflags.patch-new/lib/Kconfig
@@ -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
@@ -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

It looks like total overkill for a simple problem to me. And is there really any other user of this other than swsusp?

-Andi

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

We'll probably end up needing a similar mechanism for memory hotplug. What I need is a mechanism that is exceedingly quick during normal runtime, any maybe marginally slower during a memory remove operation.

We basically put three or so hooks into some crucial parts of the page allocator to grab out pages which we want to remove so that they never make it back into the allocator or out to the system.

Those hooks have to be _really_ fast at runtime, obviously. In my testing code, I always just added a page flag, but that's only because I was being lazy when I coded it up.

-- Dave

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Hi.

Sorry for the slow response. I switched email clients and gained a bogus filter along the way (entirely my fault, of course).

As Dave said, he might make use of them too. I use about 5 or 6 of these, depending upon exactly how Suspend2 is configured.

In the meanwhile, AKPM gave me a suggestion for a better solution (radix-trees). My algorithms & data-structures course was 14 years ago, so I'll go dust off Kingston (IIRC) and learn what he's talking about again :)

Thanks for the feedback and regards,

Nigel

Hi Nigel,

I like the idea of the patch, but the code looks a bit too complicated IMO. What is wrong with using vmalloc() to allocate a virtual contiguous range of 0-order pages (one bit per page), and then use the functions in linux/bitmap.h...? Or maybe I'm misunderstanding.

A system that has 2 GB RAM and 4 KB pages would use 64 KB per bitmap (one bitmap per node), which is not so bad memory wise if you plan to use all bits.

OTOH, if your plan is to use a single bit here and there, and leave most of the bits unused then some kind of tree is probably better.

Or does the kernel already implement some kind of data structure that never consumes _that_ much more space than a bitmap when fully used, and saves a lot of memory when just sparsely populated?

/ magnus

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Hi.

Thanks for the suggestion - I'll look into it too.

Part of my reason for implementing them in this way was to make serialising the data in an image header easy, when suspending to disk. I use the bitmaps to record which pages were atomically copied, and generate a similar bitmap for addresses of the freshly loaded pages prior to restoring the image at resume time. Of course the routines that does the atomic restore also iterates through these bitmaps. I'm not sure whether that changes anything, but thought it was worth mentioning.

Regards,

Nigel