[RFC][PATCH] Dynamically allocated pageflags.

[RFC][PATCH] Dynamically allocated pageflags.

[Nigel Cunningham]

Hi all.

For some time now, we've been running out of bits for pageflags.

In Suspend2, I need the functional equivalent of pageflags, but don't
need them when Suspend isn't running. One of the outcomes of the last
submission of Suspend2 for review was that I changed the format in which
that data is stored, creating something I call dynamically allocated
pageflags.

It's a simple idea: we tie together a bunch of order zero allocated
pages using a kmalloc'd list of poiinters to those pages, and store the
location of that kmalloc'd list in what's really an unsigned long **
(typedef'd). We also provide macros so that calls for setting and
clearing flags can look just like ordinary pageflag set/clear/test
invocations.

Helpers are also provided for allocating and freeing the maps.

Speaking with Dave Hansen this morning on IRC prompted me to send this
ahead of the rest of Suspend2 (I hope to do another submission soon), so
that he (and perhaps others) can utilise it in the mean time. A couple
of obvious candidates for using these flags are the Nosave and
NoSaveFree flags.

I make no claim that the calculations are done in the most efficient
way; just that it works and is well tested.

For sample usage, see the example in dyn_pageflags.h.

Regards,

Nigel

diff -ruNp 992-dynamic-pageflags-old/include/linux/dyn_pageflags.h 992-dynamic-pageflags-new/include/linux/dyn_pageflags.h
--- 992-dynamic-pageflags-old/include/linux/dyn_pageflags.h	1970-01-01 10:00:00.000000000 +1000
+++ 992-dynamic-pageflags-new/include/linux/dyn_pageflags.h	2005-02-19 13:11:31.000000000 +1100
@@ -0,0 +1,47 @@
+/*
+ * include/linux/dyn_pageflags.h
+ *
+ * Copyright (C) 2004-2005 Nigel Cunningham <ncunningham@cyclades.com>
+ *
+ * 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.
+ */
+
+#include <linux/mm.h>
+
+typedef unsigned long ** dyn_pageflags_t;
+
+#define BITNUMBER(page) (page_to_pfn(page))
+
+#define PAGEBIT(page) ((int) ((page_to_pfn(page))%(8 * sizeof(unsigned long))))
+
+#define BITS_PER_PAGE (PAGE_SIZE * 8)
+#define PAGES_PER_BITMAP ((max_mapnr + BITS_PER_PAGE - 1) / BITS_PER_PAGE)
+#define PAGENUMBER(page) (BITNUMBER(page) / BITS_PER_PAGE)
+
+#define PAGEINDEX(page) ((BITNUMBER(page) - (BITS_PER_PAGE * PAGENUMBER(page)))/(8*sizeof(unsigned long)))
+
+#define PAGE_UL_PTR(bitmap, pagenum) ((bitmap[PAGENUMBER(pagenum)])+PAGEINDEX(pagenum))
+
+/* With the above macros defined, you can do...
+
+#define PageInUse(page)	\
+	test_bit(PAGEBIT(page), PAGE_UL_PTR(in_use_map, page))
+#define SetPageInUse(page) \
+	set_bit(PAGEBIT(page), PAGE_UL_PTR(in_use_map, page))
+#define ClearPageInUse(page) \
+	clear_bit(PAGEBIT(page), PAGE_UL_PTR(in_use_map, page))
+*/
+
+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);
+
+/* Used by Suspend2 */
+extern void save_dyn_pageflags(dyn_pageflags_t pagemap);
+extern void load_dyn_pageflags(dyn_pageflags_t pagemap);
+void relocate_dyn_pageflags(dyn_pageflags_t *pagemap);
+int compare_dyn_pageflags(dyn_pageflags_t map1, dyn_pageflags_t map2);
diff -ruNp 992-dynamic-pageflags-old/lib/dyn_pageflags.c 992-dynamic-pageflags-new/lib/dyn_pageflags.c
--- 992-dynamic-pageflags-old/lib/dyn_pageflags.c	1970-01-01 10:00:00.000000000 +1000
+++ 992-dynamic-pageflags-new/lib/dyn_pageflags.c	2005-02-19 13:11:31.000000000 +1100
@@ -0,0 +1,82 @@
+/*
+ * lib/dyn_pageflags.c
+ *
+ * Copyright (C) 2004-2005 Nigel Cunningham <ncunningham@cyclades.com>
+ * 
+ * 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>
+
+/* clear_map
+ *
+ * Description:	Clear an array used to store local page flags.
+ * Arguments:	dyn_pageflags_t:	The pagemap to be cleared.
+ */
+
+void clear_dyn_pageflags(dyn_pageflags_t pagemap)
+{
+	int i = 0;
+	
+	for (i = 0; i < PAGES_PER_BITMAP; i++)
+		memset((pagemap[i]), 0, PAGE_SIZE);
+}
+
+/* allocate_local_pageflags
+ *
+ * Description:	Allocate a bitmap for local page flags.
+ * Arguments:	dyn_pageflags_t *:	Pointer to the bitmap.
+ */
+int allocate_dyn_pageflags(dyn_pageflags_t *pagemap)
+{
+	int i;
+
+	BUG_ON(*pagemap);
+
+	*pagemap = kmalloc(sizeof(void *) * PAGES_PER_BITMAP, GFP_ATOMIC);
+
+	for (i = 0; i < PAGES_PER_BITMAP; i++) {
+		(*pagemap)[i] = (unsigned long *) get_zeroed_page(GFP_ATOMIC);
+		if (!(*pagemap)[i]) {
+			printk("Error. Unable to allocate memory for "
+					"dynamic pageflags.");
+			free_dyn_pageflags(pagemap);
+			return 1;
+		}
+	}
+	return 0;
+}
+
+/* free_dyn_pageflags
+ *
+ * Description:	Free a dynamically allocated pageflags bitmap.
+ * Arguments:	dyn_pageflags_t *: Pointer to the bitmap being freed.
+ */
+int free_dyn_pageflags(dyn_pageflags_t *pagemap)
+{
+	int i = 0;
+	if (!*pagemap)
+		return 1;
+	
+	for (i = 0; i < PAGES_PER_BITMAP; i++)
+		free_pages((unsigned long) (*pagemap)[i], 0);
+	
+	kfree(*pagemap);
+	*pagemap = NULL;
+	return 0;
+}
+
+EXPORT_SYMBOL(clear_dyn_pageflags);
+EXPORT_SYMBOL(allocate_dyn_pageflags);
+EXPORT_SYMBOL(free_dyn_pageflags);
diff -ruNp 992-dynamic-pageflags-old/lib/Makefile 992-dynamic-pageflags-new/lib/Makefile
--- 992-dynamic-pageflags-old/lib/Makefile	2005-02-19 13:18:07.000000000 +1100
+++ 992-dynamic-pageflags-new/lib/Makefile	2005-02-19 13:11:31.000000000 +1100
@@ -5,7 +5,8 @@
 lib-y := errno.o ctype.o string.o vsprintf.o cmdline.o \
 	 bust_spinlocks.o rbtree.o radix-tree.o dump_stack.o \
 	 kobject.o kref.o idr.o div64.o parser.o int_sqrt.o \
-	 bitmap.o extable.o kobject_uevent.o prio_tree.o
+	 bitmap.o extable.o kobject_uevent.o prio_tree.o \
+	 dyn_pageflags.o
 
 ifeq ($(CONFIG_DEBUG_KOBJECT),y)
 CFLAGS_kobject.o += -DDEBUG

-- 
Nigel Cunningham
Software Engineer, Canberra, Australia
http://www.cyclades.com

Ph: +61 (2) 6292 8028      Mob: +61 (417) 100 574

Re: [RFC][PATCH] Dynamically allocated pageflags.

[Dave Hansen]

On Sat, 2005-02-19 at 13:43 +1100, Nigel Cunningham wrote:
> For some time now, we've been running out of bits for pageflags.
> 
> In Suspend2, I need the functional equivalent of pageflags, but don't
> need them when Suspend isn't running. One of the outcomes of the last
> submission of Suspend2 for review was that I changed the format in which
> that data is stored, creating something I call dynamically allocated
> pageflags.
> 
> It's a simple idea: we tie together a bunch of order zero allocated
> pages using a kmalloc'd list of poiinters to those pages, and store the
> location of that kmalloc'd list in what's really an unsigned long **
> (typedef'd). We also provide macros so that calls for setting and
> clearing flags can look just like ordinary pageflag set/clear/test
> invocations.
> 
> Helpers are also provided for allocating and freeing the maps.

I'm kicking myself because I thought about this 2 minutes after we
talked on IRC.  

One issue is that it doesn't work with DISCONTIGMEM (or the upcoming
sparsemem).  max_mapnr doesn't exist on those systems, and on the really
discontiguous ones, you might be allocating very large areas with very
sparse maps.

One thing that I've been thinking about for these things is something
tree-based.  A 1 or 2-level tree, like pagetables should be fast enough,
and handle the sparse and discontiguous layouts a little better than a
flat one.  We could even do a flat bitmap for normal systems, and #ifdef
in the table only when it's needed.  I can take a look at doing this
next week.

-- Dave

Re: [RFC][PATCH] Dynamically allocated pageflags.

[Nigel Cunningham]

Hi.

On Sat, 2005-02-19 at 14:02, Dave Hansen wrote:
> On Sat, 2005-02-19 at 13:43 +1100, Nigel Cunningham wrote:
> > For some time now, we've been running out of bits for pageflags.
> > 
> > In Suspend2, I need the functional equivalent of pageflags, but don't
> > need them when Suspend isn't running. One of the outcomes of the last
> > submission of Suspend2 for review was that I changed the format in which
> > that data is stored, creating something I call dynamically allocated
> > pageflags.
> > 
> > It's a simple idea: we tie together a bunch of order zero allocated
> > pages using a kmalloc'd list of poiinters to those pages, and store the
> > location of that kmalloc'd list in what's really an unsigned long **
> > (typedef'd). We also provide macros so that calls for setting and
> > clearing flags can look just like ordinary pageflag set/clear/test
> > invocations.
> > 
> > Helpers are also provided for allocating and freeing the maps.
> 
> I'm kicking myself because I thought about this 2 minutes after we
> talked on IRC.  

> One issue is that it doesn't work with DISCONTIGMEM (or the upcoming
> sparsemem).  max_mapnr doesn't exist on those systems, and on the really
> discontiguous ones, you might be allocating very large areas with very
> sparse maps.

:> Am I right in thinking that just requires something similar, done
per-zone? If that's the case, I'll happily modify the code to suit. I
should support discontig anyway in suspend.

> One thing that I've been thinking about for these things is something
> tree-based.  A 1 or 2-level tree, like pagetables should be fast enough,
> and handle the sparse and discontiguous layouts a little better than a
> flat one.  We could even do a flat bitmap for normal systems, and #ifdef
> in the table only when it's needed.  I can take a look at doing this
> next week.

Mmm. I've got enough on my plate at the mo, so I'll just wait to see
what you come up with.

Regards,

Nigel
-- 
Nigel Cunningham
Software Engineer, Canberra, Australia
http://www.cyclades.com

Ph: +61 (2) 6292 8028      Mob: +61 (417) 100 574

Re: [RFC][PATCH] Dynamically allocated pageflags.

[Dave Hansen]

On Sat, 2005-02-19 at 14:35 +1100, Nigel Cunningham wrote:
> On Sat, 2005-02-19 at 14:02, Dave Hansen wrote:
> > One issue is that it doesn't work with DISCONTIGMEM (or the upcoming
> > sparsemem).  max_mapnr doesn't exist on those systems, and on the really
> > discontiguous ones, you might be allocating very large areas with very
> > sparse maps.
> 
> :> Am I right in thinking that just requires something similar, done
> per-zone? If that's the case, I'll happily modify the code to suit. I
> should support discontig anyway in suspend.

The mem_maps are per-pgdat or per-node with discontig, but I have a
patch in the pipeline to take them out of there and make one for every
128MB or 256MB, etc... area of memory (for memory hotplug).  So, hanging
them off the pgdat or zone won't even work in that case, because even
the struct zone can have pretty sparse memory inside of it.  I *think*
the table is the only way to go.  But, that can wait until Monday. :)

-- Dave

Re: [RFC][PATCH] Dynamically allocated pageflags.

[Nigel Cunningham]

Hi.

On Sat, 2005-02-19 at 16:51, Dave Hansen wrote:
> On Sat, 2005-02-19 at 14:35 +1100, Nigel Cunningham wrote:
> > On Sat, 2005-02-19 at 14:02, Dave Hansen wrote:
> > > One issue is that it doesn't work with DISCONTIGMEM (or the upcoming
> > > sparsemem).  max_mapnr doesn't exist on those systems, and on the really
> > > discontiguous ones, you might be allocating very large areas with very
> > > sparse maps.
> > 
> > :> Am I right in thinking that just requires something similar, done
> > per-zone? If that's the case, I'll happily modify the code to suit. I
> > should support discontig anyway in suspend.
> 
> The mem_maps are per-pgdat or per-node with discontig, but I have a
> patch in the pipeline to take them out of there and make one for every
> 128MB or 256MB, etc... area of memory (for memory hotplug).  So, hanging
> them off the pgdat or zone won't even work in that case, because even
> the struct zone can have pretty sparse memory inside of it.  I *think*
> the table is the only way to go.  But, that can wait until Monday. :)

Okay. I'll just wait :>

Nigel
-- 
Nigel Cunningham
Software Engineer, Canberra, Australia
http://www.cyclades.com

Ph: +61 (2) 6292 8028      Mob: +61 (417) 100 574

Re: [RFC][PATCH] Dynamically allocated pageflags.

[Pavel Machek]

Hi!

> In Suspend2, I need the functional equivalent of pageflags, but don't
> need them when Suspend isn't running. One of the outcomes of the last
> submission of Suspend2 for review was that I changed the format in which
> that data is stored, creating something I call dynamically allocated
> pageflags.
> 
> It's a simple idea: we tie together a bunch of order zero allocated
> pages using a kmalloc'd list of poiinters to those pages, and store the

Will not using linklist for this make some algorithms O(n^2), hidden in the
macros so that user does not realize it?
-- 
64 bytes from 195.113.31.123: icmp_seq=28 ttl=51 time=448769.1 ms         

Re: [RFC][PATCH] Dynamically allocated pageflags.

[Dave Hansen]

[-- Attachment #1: Type: text/plain, Size: 2434 bytes --]

On Sat, 2005-02-19 at 17:03 +1100, Nigel Cunningham wrote:
> > The mem_maps are per-pgdat or per-node with discontig, but I have a
> > patch in the pipeline to take them out of there and make one for every
> > 128MB or 256MB, etc... area of memory (for memory hotplug).  So, hanging
> > them off the pgdat or zone won't even work in that case, because even
> > the struct zone can have pretty sparse memory inside of it.  I *think*
> > the table is the only way to go.  But, that can wait until Monday. :)
> 
> Okay. I'll just wait :>

I didn't realize at first that your patch already did 95% of what I
wanted.  Pretty much all that has to be done is make checks in the
allocation loop to make sure that pages are present before allocating
the map space for them.

However, one use that I was thinking of would require map space for even
non-present pages: implementing something like pfn_valid() for memory
hotplug.  We'd need a bit for every page that is possible in the system,
no matter what.  So, I added a flag to the alloc routine to allow both
of these combinations.

We could also optimize the lookup side to assume that a NULL in the
top-level table implies all 0's for the second level. Then, have the
users of PAGE_UL_PTR() check for NULL results.  That would save some
memory, and another cacheline during a lookup.  

static inline unsigned long *PAGE_UL_PTR(dyn_pageflags_t *bitmap, int
pagenum)
{
	unsigned long *map = bitmap[PAGENUMBER(pagenum)];

	if (unlikely(!map))
		return NULL;

	return map + PAGEINDEX(pagenum);
}

The other thing is to replace max_mapnr with something that is friendly
for memory hotplug.  We have a way to represent the largest _possible_
physical memory with MAX_PHYSADDR_BITS.  That can be used instead of
max_mapnr to figure out how big the table has to be.  This patch isn't
merged yet, but it's where I got MAX_PHYSADDR_BITS.

http://www.sr71.net/patches/2.6.11/2.6.11-rc3-mhp1/broken-out/B-sparse-160-sparsemem-i386.patch

The only other question is how much memory this design can handle.  With
512 indexes in the top-level page (64-bit architectures), a 128k maximum
kmalloc() for the second level, and 4k pages, I think that's 2TB of
memory.  We can always use __alloc_pages() directly if we need more than
that. :)

Attached patch is untested, uncompiled, and would have to be applied
after the sparsemem patches I pointed to above, anyway.  Does it look
OK, in concept?

-- Dave

[-- Attachment #2: unflat_dyn_pageflags.patch --]
[-- Type: text/x-patch, Size: 4033 bytes --]



---

 dynpageflags-dave/include/linux/dyn_pageflags.h |   20 ++++++++++++++++++--
 dynpageflags-dave/include/linux/mmzone.h        |   13 +++++++++++++
 dynpageflags-dave/lib/dyn_pageflags.c           |   15 +++++++++++----
 3 files changed, 42 insertions(+), 6 deletions(-)

diff -puN include/linux/dyn_pageflags.h~unflat_dyn_pageflags include/linux/dyn_pageflags.h
--- dynpageflags/include/linux/dyn_pageflags.h~unflat_dyn_pageflags	2005-02-21 08:31:38.000000000 -0800
+++ dynpageflags-dave/include/linux/dyn_pageflags.h	2005-02-21 09:42:36.000000000 -0800
@@ -14,12 +14,28 @@
 
 typedef unsigned long ** dyn_pageflags_t;
 
+enum pageflags_type {
+	PRESENT_PAGES_ONLY,
+	ALL_PAGES
+};
+
 #define BITNUMBER(page) (page_to_pfn(page))
 
 #define PAGEBIT(page) ((int) ((page_to_pfn(page))%(8 * sizeof(unsigned long))))
 
 #define BITS_PER_PAGE (PAGE_SIZE * 8)
-#define PAGES_PER_BITMAP ((max_mapnr + BITS_PER_PAGE - 1) / BITS_PER_PAGE)
+
+/*
+ * This MAX_MAPNR definition should probably go in place of max_mapnr
+ * in a real mm header
+ */
+#ifdef CONFIG_FLATMEM
+#define MAX_MAPNR	 (max_mapnr)
+#else
+#define MAX_MAPNR	 (MAX_PHYSADDR_BITS-PAGE_SHIFT)
+#endif
+#define PAGES_PER_BITMAP ((MAX_MAPNR + BITS_PER_PAGE - 1) / BITS_PER_PAGE)
+
 #define PAGENUMBER(page) (BITNUMBER(page) / BITS_PER_PAGE)
 
 #define PAGEINDEX(page) ((BITNUMBER(page) - (BITS_PER_PAGE * PAGENUMBER(page)))/(8*sizeof(unsigned long)))
@@ -37,7 +53,7 @@ typedef unsigned long ** dyn_pageflags_t
 */
 
 extern void clear_dyn_pageflags(dyn_pageflags_t pagemap);
-extern int allocate_dyn_pageflags(dyn_pageflags_t *pagemap);
+extern int allocate_dyn_pageflags(dyn_pageflags_t *pagemap, enum pageflags_type);
 extern int free_dyn_pageflags(dyn_pageflags_t *pagemap);
 
 /* Used by Suspend2 */
diff -puN lib/dyn_pageflags.c~unflat_dyn_pageflags lib/dyn_pageflags.c
--- dynpageflags/lib/dyn_pageflags.c~unflat_dyn_pageflags	2005-02-21 08:31:39.000000000 -0800
+++ dynpageflags-dave/lib/dyn_pageflags.c	2005-02-21 09:42:23.000000000 -0800
@@ -38,7 +38,7 @@ void clear_dyn_pageflags(dyn_pageflags_t
  * Description:	Allocate a bitmap for local page flags.
  * Arguments:	dyn_pageflags_t *:	Pointer to the bitmap.
  */
-int allocate_dyn_pageflags(dyn_pageflags_t *pagemap)
+int allocate_dyn_pageflags(dyn_pageflags_t *pagemap, enum pageflags_type type)
 {
 	int i;
 
@@ -47,12 +47,17 @@ int allocate_dyn_pageflags(dyn_pageflags
 	*pagemap = kmalloc(sizeof(void *) * PAGES_PER_BITMAP, GFP_ATOMIC);
 
 	for (i = 0; i < PAGES_PER_BITMAP; i++) {
+		int pfn = i * BITS_PER_PAGE;
+		if ((type == PRESENT_PAGES_ONLY) &&
+		    !pfn_valid_range(i, i + BITS_PER_PAGE))
+			continue;
+
 		(*pagemap)[i] = (unsigned long *) get_zeroed_page(GFP_ATOMIC);
 		if (!(*pagemap)[i]) {
 			printk("Error. Unable to allocate memory for "
 					"dynamic pageflags.");
 			free_dyn_pageflags(pagemap);
-			return 1;
+			return -ENOMEM;
 		}
 	}
 	return 0;
@@ -69,8 +74,10 @@ int free_dyn_pageflags(dyn_pageflags_t *
 	if (!*pagemap)
 		return 1;
 
-	for (i = 0; i < PAGES_PER_BITMAP; i++)
-		free_pages((unsigned long) (*pagemap)[i], 0);
+	for (i = 0; i < PAGES_PER_BITMAP; i++) {
+		if (pagemap[i])
+			free_pages((unsigned long) (*pagemap)[i], 0);
+	}
 
 	kfree(*pagemap);
 	*pagemap = NULL;
diff -puN include/linux/mmzone.h~unflat_dyn_pageflags include/linux/mmzone.h
--- dynpageflags/include/linux/mmzone.h~unflat_dyn_pageflags	2005-02-21 09:16:28.000000000 -0800
+++ dynpageflags-dave/include/linux/mmzone.h	2005-02-21 09:21:18.000000000 -0800
@@ -410,6 +410,19 @@ extern struct pglist_data contig_page_da
 #error ZONES_SHIFT > MAX_ZONES_SHIFT
 #endif
 
+#ifndef CONFIG_SPARSEMEM
+static inline int pfn_valid_range(int start_pfn, int end_pfn)
+{
+	return pfn_valid(start) || pfn_valid(end);
+}
+#else
+static inline int pfn_valid_range(int start_pfn, int end_pfn)
+{
+	return valid_section_nr(start_pfn >> PAGES_PER_SECTION) ||
+	       valid_section_nr(end_pfn >> PAGES_PER_SECTION);
+}
+#endif
+
 #endif /* !__ASSEMBLY__ */
 #endif /* __KERNEL__ */
 #endif /* _LINUX_MMZONE_H */
_