Skip to contentSkip to conversation

Dynamically allocated pageflags.

RFC PATCH In review Nigel Cunningham 3 participants 7 messages Feb 19, 2005 – Feb 21, 2005

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

RFC PATCH 1/1 Dynamically allocated pageflags.

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

include/linux/dyn_pageflags.h +47 -0
diff -ruNp 992-dynamic-pageflags-old/include/linux/dyn_pageflags.h 992-dynamic-pageflags-new/include/linux/dyn_pageflags.h
@@ -0,0 +1,47 @@
+/*
+ * include/linux/dyn_pageflags.h
+ *
+ * Copyright (C) 2004-2005 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.
+ */
+
+#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);
lib/dyn_pageflags.c +82 -0

82 lines not on this page · raw message

lib/Makefile +2 -1
diff -ruNp 992-dynamic-pageflags-old/lib/Makefile 992-dynamic-pageflags-new/lib/Makefile
@@ -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
Signature · 5 lines
Nigel Cunningham
Software Engineer, Canberra, Australia
http://www.cyclades.com

Ph: +61 (2) 6292 8028      Mob: +61 (417) 100 574
#1 lore raw
Quoted 8 lines · Nigel Cunningham

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.

Quoted 8 lines

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

#2 lore raw

Hi.

Quoted 18 lines · Dave Hansen
Quoted 8 lines · Nigel Cunningham

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.

Quoted 8 lines

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.

Quoted 7 lines

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.

Quoted 6 lines

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

Signature · 5 lines
Nigel Cunningham
Software Engineer, Canberra, Australia
http://www.cyclades.com

Ph: +61 (2) 6292 8028      Mob: +61 (417) 100 574
#3 lore raw
Quoted 9 lines · Nigel Cunningham
Quoted 4 lines · Dave Hansen

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

#4 lore raw

Hi.

Quoted 11 lines · Dave Hansen
Quoted 9 lines · Nigel Cunningham
Quoted 4 lines · Dave Hansen

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.

Quoted 6 lines

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

Signature · 5 lines
Nigel Cunningham
Software Engineer, Canberra, Australia
http://www.cyclades.com

Ph: +61 (2) 6292 8028      Mob: +61 (417) 100 574
#5 lore raw
Quoted 8 lines · Nigel Cunningham
Quoted 6 lines

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

---

 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(-)
include/linux/dyn_pageflags.h renamed from include/linux/dyn_pageflags.h~unflat_dyn_pageflags +18 -2
diff -puN include/linux/dyn_pageflags.h~unflat_dyn_pageflags include/linux/dyn_pageflags.h
@@ -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 */
lib/dyn_pageflags.c renamed from lib/dyn_pageflags.c~unflat_dyn_pageflags +11 -4
diff -puN lib/dyn_pageflags.c~unflat_dyn_pageflags lib/dyn_pageflags.c
@@ -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;
include/linux/mmzone.h renamed from include/linux/mmzone.h~unflat_dyn_pageflags +13 -0
diff -puN include/linux/mmzone.h~unflat_dyn_pageflags include/linux/mmzone.h
@@ -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 */

_

#6 lore raw
In reply to Nigel Cunningham

Hi!

Quoted 8 lines

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?

Signature · 1 line
64 bytes from 195.113.31.123: icmp_seq=28 ttl=51 time=448769.1 ms