Skip to contentSkip to conversation

[] Dynamically Allocated Pageflags

Suspend2 Nigel Cunningham 2 participants 8 messages Jun 26, 2006 – Jun 28, 2006 Library code

lore
Share & tools
lore
#0 lore raw

Add support for dynamically allocated pageflags, used by Suspend2 for recording which pages are being saved in the different parts of the image and where they're being copied to/from at atomic copy time.

#1 lore raw

[Suspend2][] [Suspend2] Dynamically allocated pageflags

Add support for dynamically allocated pageflags - bitmaps consisting of single pages merged together into per zone bitmaps that can then be used as temporary page flags.

 include/linux/dyn_pageflags.h |   66 ++++++++
 lib/Kconfig                   |    3 
 lib/Makefile                  |    2 
 lib/dyn_pageflags.c           |  330 +++++++++++++++++++++++++++++++++++++++++
 4 files changed, 401 insertions(+), 0 deletions(-)
include/linux/dyn_pageflags.h new file +66 -0
new file mode 100644
index 0000000..1a7b5d8
@@ -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 > -1; \
+		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 void 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
lib/Kconfig +3 -0
index 3de9335..5596bd8 100644
@@ -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
 #
lib/Makefile +2 -0
index b830c9a..8290e9b 100644
@@ -31,6 +31,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
lib/dyn_pageflags.c new file +330 -0

330 lines not on this page · raw message

--
Nigel Cunningham nigel at suspend2 dot net

#2 lore raw

Re: [Suspend2][] [Suspend2] Dynamically allocated pageflags

Quoted 3 lines · Nigel Cunningham

Add support for dynamically allocated pageflags - bitmaps consisting of single pages merged together into per zone bitmaps that can then be used as temporary page flags.

IIRC, this has already been discussed on LKML and some people argued it would be overkill. Could you please say why you think it's not so?

Well, having read the entire patch I think I'd do this in a different way. Namely, we can always use pfn_to_page() to get the struct page corresponding to given PFN, so we can enumerate pages from 0 to max_pfn and create a simple bitmap with one or more bits per PFN. The only difficulty I see wrt this is to make sure 0-order allocations are used for the bitmaps.

Anyway you can find some comments below.

Greetings,
Rafael

Quoted 22 lines
 include/linux/dyn_pageflags.h |   66 ++++++++
 lib/Kconfig                   |    3 
 lib/Makefile                  |    2 
 lib/dyn_pageflags.c           |  330 +++++++++++++++++++++++++++++++++++++++++
 4 files changed, 401 insertions(+), 0 deletions(-)
include/linux/dyn_pageflags.h new file +8 -0
new file mode 100644
index 0000000..1a7b5d8
@@ -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

include/linux/dyn_pageflags.h line 18

Quoted 10 lines
include/linux/dyn_pageflags.h new file +10 -0
+ * 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;

Is this really necessary to define the dyn_pageflags_t here?

include/linux/dyn_pageflags.h line 20

Quoted 2 lines
include/linux/dyn_pageflags.h new file +2 -0
+
+#define BITNUMBER(page) (page_to_pfn(page))

I think it would be cleaner to use page_to_pfn(page) verbatim instead of this.

Quoted 12 lines
include/linux/dyn_pageflags.h new file +12 -0
+
+#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)

include/linux/dyn_pageflags.h line 42

Quoted 10 lines
include/linux/dyn_pageflags.h new file +10 -0
+#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))

All of the above definitions seem to be related in an opaque way. Any chance to make them a bit more clearer? A comment, maybe?

include/linux/dyn_pageflags.h line 49

Quoted 7 lines
include/linux/dyn_pageflags.h new file +7 -0
+
+/* 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))
+*/

I'd choose different names for these. Also the definitions shouldn't go before test/set/clear_dynpageflag() are defined, IMO.

Quoted 82 lines
include/linux/dyn_pageflags.h new file +17 -0
+
+#define BITMAP_FOR_EACH_SET(bitmap, counter) \
+	for (counter = get_next_bit_on(bitmap, -1); counter > -1; \
+		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 void 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
lib/Kconfig +3 -0
index 3de9335..5596bd8 100644
@@ -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
 #
lib/Makefile +2 -0
index b830c9a..8290e9b 100644
@@ -31,6 +31,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
lib/dyn_pageflags.c new file +32 -0
new file mode 100644
index 0000000..4da52f5
@@ -0,0 +1,330 @@
+/*
+ * lib/dyn_pageflags.c
+ *
+ * Copyright (C) 2004-2006 Nigel Cunningham <[email protected]>
+ * 
+ * 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?
+ *
+ */
+

lib/dyn_pageflags.c line 42

Quoted 10 lines
lib/dyn_pageflags.c new file +10 -0
+static int num_zones(void)
+{
+	int result = 0;
+	struct zone *zone;
+
+	for_each_zone(zone)
+		result++;
+
+	return result;
+}

Do we really need this?

lib/dyn_pageflags.c line 55

Quoted 13 lines
lib/dyn_pageflags.c new file +13 -0
+
+/* 
+ * 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);
+}

Could you please explain the maths above?

Quoted 14 lines
lib/dyn_pageflags.c new file +14 -0
+
+/*
+ * 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)

lib/dyn_pageflags.c line 79

Quoted 10 lines
lib/dyn_pageflags.c new file +10 -0
+		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;
+}

Why can't we use page_zonenum() instead of this?

Quoted 7 lines
lib/dyn_pageflags.c new file +7 -0
+
+/*
+ * dyn_pageflags_pages_per_bitmap
+ *
+ * Number of pages needed for a bitmap covering all zones.
+ *
+ */

lib/dyn_pageflags.c line 96

Quoted 10 lines
lib/dyn_pageflags.c new file +10 -0
+int dyn_pageflags_pages_per_bitmap(void)
+{
+	int total = 0;
+	struct zone *zone;
+
+	for_each_zone(zone)
+		total += pages_for_zone(zone);
+
+	return total;
+}

Why is a separate function needed for this?

Quoted 11 lines
lib/dyn_pageflags.c new file +11 -0
+
+/* 
+ * 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;

lib/dyn_pageflags.c line 117

Quoted 10 lines
lib/dyn_pageflags.c new file +10 -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++;
+	}
+}

I think this could be done in a simpler way too.

Quoted 5 lines
lib/dyn_pageflags.c new file +5 -0
+
+/* 
+ * allocate_dyn_pageflags(dyn_pageflags_t *pagemap)
+ *
+ * Allocate a bitmap for dynamic page flags.

lib/dyn_pageflags.c line 132

Quoted 10 lines
lib/dyn_pageflags.c new file +10 -0
+ *
+ */
+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);

By using kmalloc(), you use slab. I'd rather allocate entire pages.

lib/dyn_pageflags.c line 143

Quoted 11 lines
lib/dyn_pageflags.c new file +11 -0
+
+	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);

This seems to leak memory, eg. if *pagemap[0] is allocated, but the allocation of *pagemap[1] fails. You should free *pagemap[j] up to zone_num-1 and then *pagemap, IMO.

Quoted 47 lines
lib/dyn_pageflags.c new file +47 -0
+			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]);

lib/dyn_pageflags.c line 200

Quoted 10 lines
lib/dyn_pageflags.c new file +10 -0
+		else
+			free_page((unsigned long) (*pagemap)[zone_num]);
+
+		zone_num++;
+	}
+
+	if (PageSlab(virt_to_page((*pagemap))))
+		kfree(*pagemap);
+	else
+		free_page((unsigned long) (*pagemap));

Why so?

Quoted 11 lines
lib/dyn_pageflags.c new file +11 -0
+
+	*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.
+ *

lib/dyn_pageflags.c line 221

Quoted 10 lines
lib/dyn_pageflags.c new file +10 -0
+ */
+
+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;
+}

It doesn't look very efficient, does it? ;-)

Quoted 89 lines
lib/dyn_pageflags.c new file +89 -0
+
+/*
+ * 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 -1.
+ *
+ */
+
+int get_next_bit_on(dyn_pageflags_t bitmap, int counter)
+{
+	struct page *page;
+	struct zone *zone;
+	unsigned long *ul = NULL;
+	int zone_offset, pagebit, zone_num, first;
+
+	first = (counter == -1);
+	
+	if (first)
+		counter = first_online_pgdat()->node_zones->zone_start_pfn;
+
+	page = pfn_to_page(counter);
+	zone = page_zone(page);
+	zone_num = page_zone_number(page);
+	zone_offset = counter - zone->zone_start_pfn;
+
+	if (first) {
+		counter--;
+		zone_offset--;
+	} else
+		ul = (bitmap[zone_num][PAGENUMBER(zone_offset)]) + PAGEINDEX(zone_offset);
+
+	do {
+		counter++;
+		zone_offset++;
+	
+		if (zone_offset >= zone->spanned_pages) {
+			do {
+				zone = next_zone(zone);
+				if (!zone)
+					return -1;
+				zone_num++;
+			} while(!zone->spanned_pages);

lib/dyn_pageflags.c line 320

Quoted 10 lines
lib/dyn_pageflags.c new file +10 -0
+
+			counter = zone->zone_start_pfn;
+			zone_offset = 0;
+		}
+		
+		/*
+		 * This could be optimised, but there are more
+		 * important things and the code is simple at
+		 * the moment 
+		 */

Please let me disagree with this comment. I think it would be more efficient if you searched the bitmap for the first zero bit and then find the page, pfn, whatever corresponding to this bit.

Quoted 10 lines
lib/dyn_pageflags.c new file +10 -0
+		pagebit = PAGEBIT(zone_offset);
+
+		if (!pagebit)
+			ul = (bitmap[zone_num][PAGENUMBER(zone_offset)]) + PAGEINDEX(zone_offset);
+
+	} while(!test_bit(pagebit, ul));
+
+	return counter;
+}
+
#3 lore raw

Re: [Suspend2][] [Suspend2] Dynamically allocated pageflags

Hi.

Quoted 7 lines · Rafael J. Wysocki
Quoted 3 lines · Nigel Cunningham

Add support for dynamically allocated pageflags - bitmaps consisting of single pages merged together into per zone bitmaps that can then be used as temporary page flags.

IIRC, this has already been discussed on LKML and some people argued it would be overkill. Could you please say why you think it's not so?

Some people did, but IIRC, Dave Jones liked the general idea. The main rationale was that we have a limited number of pageflags, and this provides a way that we can easily add new ones without expanding struct page. Obviously it's better for usage patterns like suspend2.

The other (suspend2 specific) advantage is that having them stored like this makes storing the image data much simpler and while we're calculating the contents of the image, there is zero impact on the size of this metadata storage from changes in the pages that are in each pagedir.

Quoted 6 lines

Well, having read the entire patch I think I'd do this in a different way. Namely, we can always use pfn_to_page() to get the struct page corresponding to given PFN, so we can enumerate pages from 0 to max_pfn and create a simple bitmap with one or more bits per PFN. The only difficulty I see wrt this is to make sure 0-order allocations are used for the bitmaps.

I used to do that, but it arm pfns don't start at zero and it would leave gaps/wastage in the discontig mem case.

Quoted 32 lines

Anyway you can find some comments below.

Greetings,
Rafael

Quoted 27 lines
 include/linux/dyn_pageflags.h |   66 ++++++++
 lib/Kconfig                   |    3
 lib/Makefile                  |    2
 lib/dyn_pageflags.c           |  330

+++++++++++++++++++++++++++++++++++++++++ 4 files changed, 401 insertions(+), 0 deletions(-)

(quoted diff) +0 -0

b/include/linux/dyn_pageflags.h new file mode 100644 index 0000000..1a7b5d8

include/linux/dyn_pageflags.h new file +12 -0
@@ -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.
+ */
+
Quoted 8 lines

include/linux/dyn_pageflags.h line 18

Quoted 6 lines
include/linux/dyn_pageflags.h new file +6 -0
+#ifndef DYN_PAGEFLAGS_H
+#define DYN_PAGEFLAGS_H
+
+#include <linux/mm.h>
+
+typedef unsigned long *** dyn_pageflags_t;

Is this really necessary to define the dyn_pageflags_t here?

This will also be used in Suspend2's kernel/power/pageflags.c, which adds support for saving the pageflags in the image header and reloading and relocating them at resume time.

Quoted 5 lines

include/linux/dyn_pageflags.h line 20

Quoted 2 lines
include/linux/dyn_pageflags.h new file +2 -0
+
+#define BITNUMBER(page) (page_to_pfn(page))

I think it would be cleaner to use page_to_pfn(page) verbatim instead of this.

I was going for readability.

Quoted 17 lines
Quoted 17 lines
include/linux/dyn_pageflags.h new file +17 -0
+
+#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))
Quoted 8 lines

include/linux/dyn_pageflags.h line 42

Quoted 5 lines
include/linux/dyn_pageflags.h new file +5 -0
+#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))

All of the above definitions seem to be related in an opaque way. Any chance to make them a bit more clearer? A comment, maybe?

Ok.

Quoted 10 lines

include/linux/dyn_pageflags.h line 49

Quoted 7 lines
include/linux/dyn_pageflags.h new file +7 -0
+
+/* 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))
+*/

I'd choose different names for these. Also the definitions shouldn't go before test/set/clear_dynpageflag() are defined, IMO.

I was seeking to make them similar to the real pageflags semantics. Did you notice that this is a comment? Will rearrange anyway.

Quoted 86 lines
Quoted 86 lines
include/linux/dyn_pageflags.h new file +16 -0
+
+#define BITMAP_FOR_EACH_SET(bitmap, counter) \
+	for (counter = get_next_bit_on(bitmap, -1); counter > -1; \
+		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 void 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

lib/Kconfig +3 -0
index 3de9335..5596bd8 100644
@@ -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
 #
lib/Makefile +2 -0
index b830c9a..8290e9b 100644
@@ -31,6 +31,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
lib/dyn_pageflags.c new file +24 -0
new file mode 100644
index 0000000..4da52f5
@@ -0,0 +1,330 @@
+/*
+ * lib/dyn_pageflags.c
+ *
+ * Copyright (C) 2004-2006 Nigel Cunningham <[email protected]>
+ *
+ * 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) +

lib/dyn_pageflags.c new file +11 -0
+/*
+ * num_zones
+ *
+ * How many zones are there?
+ *
+ */
+
+static int num_zones(void)
+{
+	int result = 0;
+	struct zone *zone;
Quoted 8 lines

lib/dyn_pageflags.c line 42

Quoted 6 lines
lib/dyn_pageflags.c new file +6 -0
+
+	for_each_zone(zone)
+		result++;
+
+	return result;
+}

Do we really need this?

Well, I need to know how many zones there are, and haven't seen a generic function. If you know of one, please point me to it. (Or I could shift this somewhere else and make it a generic function - I'm aware that I have something similar in pageflags.c).

Quoted 7 lines
Quoted 7 lines
lib/dyn_pageflags.c new file +7 -0
+
+/*
+ * pages_for_zone(struct zone *zone)
+ *
+ * How many pages do we need for a bitmap for this zone?
+ *
+ */
Quoted 8 lines

lib/dyn_pageflags.c line 55

Quoted 6 lines
lib/dyn_pageflags.c new file +6 -0
+
+static int pages_for_zone(struct zone *zone)
+{
+	return (zone->spanned_pages + (PAGE_SIZE << 3) - 1) >>
+			(PAGE_SHIFT + 3);
+}

Could you please explain the maths above?

Sure. Page_size << 3 is the number of bits in a page. We are calculating the number of pages needed to store spanned_pages bits, which is (spanned_pages + bits_per_page - 1) / (bits_per_page - 1). (Rounds up).

Quoted 18 lines
Quoted 18 lines
lib/dyn_pageflags.c new file +18 -0
+
+/*
+ * 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++;
Quoted 8 lines

lib/dyn_pageflags.c line 79

Quoted 6 lines
lib/dyn_pageflags.c new file +6 -0
+
+	printk("Was looking for a zone for page %p.\n", page);
+	BUG_ON(1);
+
+	return 0;
+}

Why can't we use page_zonenum() instead of this?

They will only be the same thing in the x86 case. If you have multiple zones and some don't have any dma pages or highmem pages, this will give a more compact numbering.

Quoted 11 lines
Quoted 11 lines
lib/dyn_pageflags.c new file +11 -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;
Quoted 8 lines

lib/dyn_pageflags.c line 96

Quoted 6 lines
lib/dyn_pageflags.c new file +6 -0
+
+	for_each_zone(zone)
+		total += pages_for_zone(zone);
+
+	return total;
+}

Why is a separate function needed for this?

Readability. Actually, answering this made me check again, and I couldn't find a user of this function. I'll remove it.

Quoted 33 lines
Quoted 11 lines
lib/dyn_pageflags.c new file +11 -0
+
+/*
+ * 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;

lib/dyn_pageflags.c line 117

Quoted 10 lines
lib/dyn_pageflags.c new file +10 -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++;
+	}
+}

I think this could be done in a simpler way too.

Quoted 9 lines
lib/dyn_pageflags.c new file +9 -0
+
+/*
+ * allocate_dyn_pageflags(dyn_pageflags_t *pagemap)
+ *
+ * Allocate a bitmap for dynamic page flags.
+ *
+ */
+int allocate_dyn_pageflags(dyn_pageflags_t *pagemap)
+{
Quoted 8 lines

lib/dyn_pageflags.c line 132

Quoted 6 lines
lib/dyn_pageflags.c new file +6 -0
+	int i, zone_num = 0;
+	struct zone *zone;
+
+	BUG_ON(*pagemap);
+
+	*pagemap = kmalloc(sizeof(void *) * num_zones(), GFP_ATOMIC);

By using kmalloc(), you use slab. I'd rather allocate entire pages.

You might only be using 20 bytes out of the page. At resume time, I do use entire pages if the kmalloc'd value needs relocating, but only if that's needed.

Quoted 7 lines
Quoted 7 lines
lib/dyn_pageflags.c new file +7 -0
+
+	if (!*pagemap)
+		return -ENOMEM;
+
+	for_each_zone(zone) {
+		int zone_pages = pages_for_zone(zone);
+		(*pagemap)[zone_num] = kmalloc(sizeof(void *) * zone_pages,
Quoted 8 lines

lib/dyn_pageflags.c line 143

Quoted 4 lines
lib/dyn_pageflags.c new file +4 -0
+					       GFP_ATOMIC);
+
+		if (!(*pagemap)[zone_num]) {
+			kfree (*pagemap);

This seems to leak memory, eg. if *pagemap[0] is allocated, but the allocation of *pagemap[1] fails. You should free *pagemap[j] up to zone_num-1 and then *pagemap, IMO.

Yes, I should. Thanks.

Quoted 51 lines
Quoted 51 lines
lib/dyn_pageflags.c new file +51 -0
+			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++;
Quoted 8 lines

lib/dyn_pageflags.c line 200

Quoted 6 lines
lib/dyn_pageflags.c new file +6 -0
+	}
+
+	if (PageSlab(virt_to_page((*pagemap))))
+		kfree(*pagemap);
+	else
+		free_page((unsigned long) (*pagemap));

Why so?

See above (Suspend2 relocation at resume time).

Quoted 15 lines
Quoted 15 lines
lib/dyn_pageflags.c new file +14 -0
+
+	*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) +{

Quoted 8 lines

lib/dyn_pageflags.c line 221

Quoted 6 lines
lib/dyn_pageflags.c new file +6 -0
+	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;
+}

It doesn't look very efficient, does it? ;-)

Readability again. I'm assuming the compiler is semi intelligent :)

Quoted 95 lines
Quoted 95 lines
lib/dyn_pageflags.c new file +77 -0
+
+/*
+ * 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 -1.
+ *
+ */
+
+int get_next_bit_on(dyn_pageflags_t bitmap, int counter)
+{
+	struct page *page;
+	struct zone *zone;
+	unsigned long *ul = NULL;
+	int zone_offset, pagebit, zone_num, first;
+
+	first = (counter == -1);
+
+	if (first)
+		counter = first_online_pgdat()->node_zones->zone_start_pfn;
+
+	page = pfn_to_page(counter);
+	zone = page_zone(page);
+	zone_num = page_zone_number(page);
+	zone_offset = counter - zone->zone_start_pfn;
+
+	if (first) {
+		counter--;
+		zone_offset--;
+	} else
+		ul = (bitmap[zone_num][PAGENUMBER(zone_offset)]) +

PAGEINDEX(zone_offset); +

lib/dyn_pageflags.c new file +17 -0
+	do {
+		counter++;
+		zone_offset++;
+
+		if (zone_offset >= zone->spanned_pages) {
+			do {
+				zone = next_zone(zone);
+				if (!zone)
+					return -1;
+				zone_num++;
+			} while(!zone->spanned_pages);
+
+			counter = zone->zone_start_pfn;
+			zone_offset = 0;
+		}
+
+		/*
Quoted 8 lines

lib/dyn_pageflags.c line 320

Quoted 4 lines
lib/dyn_pageflags.c new file +4 -0
+		 * This could be optimised, but there are more
+		 * important things and the code is simple at
+		 * the moment
+		 */

Please let me disagree with this comment. I think it would be more efficient if you searched the bitmap for the first zero bit and then find the page, pfn, whatever corresponding to this bit.

Yes, it would be more efficient. I don't mind modifying it. This is a different moment to the one when I wrote that :)

Quoted 10 lines

lib/dyn_pageflags.c line 330

Quoted 10 lines
lib/dyn_pageflags.c new file +4 -0
+		pagebit = PAGEBIT(zone_offset);
+
+		if (!pagebit)
+			ul = (bitmap[zone_num][PAGENUMBER(zone_offset)]) +

PAGEINDEX(zone_offset); +

lib/dyn_pageflags.c new file +5 -0
+	} while(!test_bit(pagebit, ul));
+
+	return counter;
+}
+

Once again,

Thanks for your feedback. It's good to get picked up on cleanups I've missed and be made to remember again and provide the justification for decisions I've made.

Regards,

Nigel

Signature · 2 lines
See http://www.suspend2.net for Howtos, FAQs, mailing
lists, wiki and bugzilla info.
#4 lore raw

Re: [Suspend2][] [Suspend2] Dynamically allocated pageflags

Hi,

Quoted 6 lines · Nigel Cunningham
Quoted 5 lines · Rafael J. Wysocki
Quoted 3 lines · Nigel Cunningham

Add support for dynamically allocated pageflags - bitmaps consisting of single pages merged together into per zone bitmaps that can then be used as temporary page flags.

Quoted 7 lines
Quoted 2 lines

IIRC, this has already been discussed on LKML and some people argued it would be overkill. Could you please say why you think it's not so?

Some people did, but IIRC, Dave Jones liked the general idea. The main rationale was that we have a limited number of pageflags, and this provides a way that we can easily add new ones without expanding struct page. Obviously it's better for usage patterns like suspend2.

Well, I think that might only be useful for "temporary" flags, because if such a structure were to stay in memory permanently, it would be better to expand struct page anyway.

Quoted 4 lines

The other (suspend2 specific) advantage is that having them stored like this makes storing the image data much simpler and while we're calculating the contents of the image, there is zero impact on the size of this metadata storage from changes in the pages that are in each pagedir.

The question is if there are any potential users of this, except for suspend2. If not, it probably would make sense to use a more suspend2-specific and maybe simpler data structure and give up the generality.

Quoted 9 lines
Quoted 6 lines

Well, having read the entire patch I think I'd do this in a different way. Namely, we can always use pfn_to_page() to get the struct page corresponding to given PFN, so we can enumerate pages from 0 to max_pfn and create a simple bitmap with one or more bits per PFN. The only difficulty I see wrt this is to make sure 0-order allocations are used for the bitmaps.

I used to do that, but it arm pfns don't start at zero and it would leave gaps/wastage in the discontig mem case.

Would that be a big problem? That is, how many bits we would waste eg. on ARM?

Quoted 36 lines
Quoted 27 lines
Quoted 27 lines
 include/linux/dyn_pageflags.h |   66 ++++++++
 lib/Kconfig                   |    3
 lib/Makefile                  |    2
 lib/dyn_pageflags.c           |  330

+++++++++++++++++++++++++++++++++++++++++ 4 files changed, 401 insertions(+), 0 deletions(-)

(quoted diff) +0 -0

b/include/linux/dyn_pageflags.h new file mode 100644 index 0000000..1a7b5d8

include/linux/dyn_pageflags.h new file +12 -0
@@ -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.
+ */
+
Quoted 8 lines

include/linux/dyn_pageflags.h line 18

Quoted 6 lines
include/linux/dyn_pageflags.h new file +6 -0
+#ifndef DYN_PAGEFLAGS_H
+#define DYN_PAGEFLAGS_H
+
+#include <linux/mm.h>
+
+typedef unsigned long *** dyn_pageflags_t;

Is this really necessary to define the dyn_pageflags_t here?

Quoted 3 lines

This will also be used in Suspend2's kernel/power/pageflags.c, which adds support for saving the pageflags in the image header and reloading and relocating them at resume time.

I would probably use unsigned long *** directly anyway.

Quoted 7 lines
Quoted 5 lines

include/linux/dyn_pageflags.h line 20

Quoted 2 lines
include/linux/dyn_pageflags.h new file +2 -0
+
+#define BITNUMBER(page) (page_to_pfn(page))

I think it would be cleaner to use page_to_pfn(page) verbatim instead of this.

I was going for readability.

Well, if I see BITNUMBER(page), I tend to check what it means, so I have to browse the code just to find out it's page_to_pfn(page). Ouch.

Quoted 39 lines
Quoted 17 lines
Quoted 17 lines
include/linux/dyn_pageflags.h new file +17 -0
+
+#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))
Quoted 8 lines

include/linux/dyn_pageflags.h line 42

Quoted 5 lines
include/linux/dyn_pageflags.h new file +5 -0
+#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))

All of the above definitions seem to be related in an opaque way. Any chance to make them a bit more clearer? A comment, maybe?

Ok.

Quoted 10 lines

include/linux/dyn_pageflags.h line 49

Quoted 7 lines
include/linux/dyn_pageflags.h new file +7 -0
+
+/* 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))
+*/

I'd choose different names for these. Also the definitions shouldn't go before test/set/clear_dynpageflag() are defined, IMO.

Quoted 2 lines

I was seeking to make them similar to the real pageflags semantics. Did you notice that this is a comment?

I didn't, sorry. Anyway it's a bit confusing.

Quoted 1 line

Will rearrange anyway.

OK

Quoted 95 lines
Quoted 86 lines
Quoted 86 lines
include/linux/dyn_pageflags.h new file +16 -0
+
+#define BITMAP_FOR_EACH_SET(bitmap, counter) \
+	for (counter = get_next_bit_on(bitmap, -1); counter > -1; \
+		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 void 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

lib/Kconfig +3 -0
index 3de9335..5596bd8 100644
@@ -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
 #
lib/Makefile +2 -0
index b830c9a..8290e9b 100644
@@ -31,6 +31,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
lib/dyn_pageflags.c new file +24 -0
new file mode 100644
index 0000000..4da52f5
@@ -0,0 +1,330 @@
+/*
+ * lib/dyn_pageflags.c
+ *
+ * Copyright (C) 2004-2006 Nigel Cunningham <[email protected]>
+ *
+ * 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) +

lib/dyn_pageflags.c new file +11 -0
+/*
+ * num_zones
+ *
+ * How many zones are there?
+ *
+ */
+
+static int num_zones(void)
+{
+	int result = 0;
+	struct zone *zone;
Quoted 8 lines

lib/dyn_pageflags.c line 42

Quoted 6 lines
lib/dyn_pageflags.c new file +6 -0
+
+	for_each_zone(zone)
+		result++;
+
+	return result;
+}

Do we really need this?

Quoted 4 lines

Well, I need to know how many zones there are, and haven't seen a generic function. If you know of one, please point me to it. (Or I could shift this somewhere else and make it a generic function - I'm aware that I have something similar in pageflags.c).

I don't know such a function, but if you need to call the above more than once it's plain inefficient. I'd define a variable num_zones instead.

Quoted 16 lines
Quoted 7 lines
Quoted 7 lines
lib/dyn_pageflags.c new file +7 -0
+
+/*
+ * pages_for_zone(struct zone *zone)
+ *
+ * How many pages do we need for a bitmap for this zone?
+ *
+ */
Quoted 8 lines

lib/dyn_pageflags.c line 55

Quoted 6 lines
lib/dyn_pageflags.c new file +6 -0
+
+static int pages_for_zone(struct zone *zone)
+{
+	return (zone->spanned_pages + (PAGE_SIZE << 3) - 1) >>
+			(PAGE_SHIFT + 3);
+}

Could you please explain the maths above?

Quoted 3 lines

Sure. Page_size << 3 is the number of bits in a page. We are calculating the number of pages needed to store spanned_pages bits, which is (spanned_pages + bits_per_page - 1) / (bits_per_page - 1). (Rounds up).

Any chance to use DIV_ROUND_UP here?

Quoted 27 lines
Quoted 18 lines
Quoted 18 lines
lib/dyn_pageflags.c new file +18 -0
+
+/*
+ * 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++;
Quoted 8 lines

lib/dyn_pageflags.c line 79

Quoted 6 lines
lib/dyn_pageflags.c new file +6 -0
+
+	printk("Was looking for a zone for page %p.\n", page);
+	BUG_ON(1);
+
+	return 0;
+}

Why can't we use page_zonenum() instead of this?

Quoted 3 lines

They will only be the same thing in the x86 case. If you have multiple zones and some don't have any dma pages or highmem pages, this will give a more compact numbering.

But this is _really_ inefficient, because you call it for every page and for how many times? I think it should be fixed.

Quoted 65 lines
Quoted 11 lines
Quoted 11 lines
lib/dyn_pageflags.c new file +11 -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;
Quoted 8 lines

lib/dyn_pageflags.c line 96

Quoted 6 lines
lib/dyn_pageflags.c new file +6 -0
+
+	for_each_zone(zone)
+		total += pages_for_zone(zone);
+
+	return total;
+}

Why is a separate function needed for this?

Readability. Actually, answering this made me check again, and I couldn't find a user of this function. I'll remove it.

Quoted 33 lines
Quoted 11 lines
lib/dyn_pageflags.c new file +11 -0
+
+/*
+ * 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;

lib/dyn_pageflags.c line 117

Quoted 10 lines
lib/dyn_pageflags.c new file +10 -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++;
+	}
+}

I think this could be done in a simpler way too.

Quoted 9 lines
lib/dyn_pageflags.c new file +9 -0
+
+/*
+ * allocate_dyn_pageflags(dyn_pageflags_t *pagemap)
+ *
+ * Allocate a bitmap for dynamic page flags.
+ *
+ */
+int allocate_dyn_pageflags(dyn_pageflags_t *pagemap)
+{
Quoted 8 lines

lib/dyn_pageflags.c line 132

Quoted 6 lines
lib/dyn_pageflags.c new file +6 -0
+	int i, zone_num = 0;
+	struct zone *zone;
+
+	BUG_ON(*pagemap);
+
+	*pagemap = kmalloc(sizeof(void *) * num_zones(), GFP_ATOMIC);

By using kmalloc(), you use slab. I'd rather allocate entire pages.

Quoted 3 lines

You might only be using 20 bytes out of the page. At resume time, I do use entire pages if the kmalloc'd value needs relocating, but only if that's needed.

Which is not exactly straightforward. IMHO that should be simplified somehow.

Quoted 79 lines
Quoted 16 lines

lib/dyn_pageflags.c line 143

Quoted 12 lines
lib/dyn_pageflags.c new file +11 -0
+
+	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);

This seems to leak memory, eg. if *pagemap[0] is allocated, but the allocation of *pagemap[1] fails. You should free *pagemap[j] up to zone_num-1 and then *pagemap, IMO.

Yes, I should. Thanks.

Quoted 51 lines
Quoted 51 lines
lib/dyn_pageflags.c new file +51 -0
+			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++;
Quoted 8 lines

lib/dyn_pageflags.c line 200

Quoted 6 lines
lib/dyn_pageflags.c new file +6 -0
+	}
+
+	if (PageSlab(virt_to_page((*pagemap))))
+		kfree(*pagemap);
+	else
+		free_page((unsigned long) (*pagemap));

Why so?

Quoted 1 line

See above (Suspend2 relocation at resume time).

Oh well ...

Quoted 24 lines
Quoted 15 lines
Quoted 15 lines
lib/dyn_pageflags.c new file +14 -0
+
+	*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) +{

Quoted 8 lines

lib/dyn_pageflags.c line 221

Quoted 6 lines
lib/dyn_pageflags.c new file +6 -0
+	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;
+}

It doesn't look very efficient, does it? ;-)

Quoted 1 line

Readability again. I'm assuming the compiler is semi intelligent :)

Well, how is it supposed to optimise out the call to page_zone_number()? Also I wouldn't bet on the efficiency of the displacement computations.

Moreover, it would be nice to avoid calling page_to_zone_offset(page) for the second time in test/set/clear_dynpageflag below.

Quoted 120 lines
Quoted 95 lines
Quoted 95 lines
lib/dyn_pageflags.c new file +77 -0
+
+/*
+ * 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 -1.
+ *
+ */
+
+int get_next_bit_on(dyn_pageflags_t bitmap, int counter)
+{
+	struct page *page;
+	struct zone *zone;
+	unsigned long *ul = NULL;
+	int zone_offset, pagebit, zone_num, first;
+
+	first = (counter == -1);
+
+	if (first)
+		counter = first_online_pgdat()->node_zones->zone_start_pfn;
+
+	page = pfn_to_page(counter);
+	zone = page_zone(page);
+	zone_num = page_zone_number(page);
+	zone_offset = counter - zone->zone_start_pfn;
+
+	if (first) {
+		counter--;
+		zone_offset--;
+	} else
+		ul = (bitmap[zone_num][PAGENUMBER(zone_offset)]) +

PAGEINDEX(zone_offset); +

lib/dyn_pageflags.c new file +17 -0
+	do {
+		counter++;
+		zone_offset++;
+
+		if (zone_offset >= zone->spanned_pages) {
+			do {
+				zone = next_zone(zone);
+				if (!zone)
+					return -1;
+				zone_num++;
+			} while(!zone->spanned_pages);
+
+			counter = zone->zone_start_pfn;
+			zone_offset = 0;
+		}
+
+		/*
Quoted 8 lines

lib/dyn_pageflags.c line 320

Quoted 4 lines
lib/dyn_pageflags.c new file +4 -0
+		 * This could be optimised, but there are more
+		 * important things and the code is simple at
+		 * the moment
+		 */

Please let me disagree with this comment. I think it would be more efficient if you searched the bitmap for the first zero bit and then find the page, pfn, whatever corresponding to this bit.

Yes, it would be more efficient. I don't mind modifying it. This is a different moment to the one when I wrote that :)

Quoted 10 lines

lib/dyn_pageflags.c line 330

Quoted 10 lines
lib/dyn_pageflags.c new file +4 -0
+		pagebit = PAGEBIT(zone_offset);
+
+		if (!pagebit)
+			ul = (bitmap[zone_num][PAGENUMBER(zone_offset)]) +

PAGEINDEX(zone_offset); +

lib/dyn_pageflags.c new file +5 -0
+	} while(!test_bit(pagebit, ul));
+
+	return counter;
+}
+

Once again,

Quoted 3 lines

Thanks for your feedback. It's good to get picked up on cleanups I've missed and be made to remember again and provide the justification for decisions I've made.

Well, unfortunately the patch doesn't look very good to me. The overall idea is quite reasonable, but IMHO the implementation needs fixing.

Greetings,
Rafael

#5 lore raw

Re: [Suspend2][] [Suspend2] Dynamically allocated pageflags

Hi.

Quoted 27 lines · Rafael J. Wysocki

Hi,

Quoted 6 lines · Nigel Cunningham
Quoted 5 lines · Rafael J. Wysocki
Quoted 3 lines · Nigel Cunningham

Add support for dynamically allocated pageflags - bitmaps consisting of single pages merged together into per zone bitmaps that can then be used as temporary page flags.

Quoted 7 lines
Quoted 2 lines

IIRC, this has already been discussed on LKML and some people argued it would be overkill. Could you please say why you think it's not so?

Some people did, but IIRC, Dave Jones liked the general idea. The main rationale was that we have a limited number of pageflags, and this provides a way that we can easily add new ones without expanding struct page. Obviously it's better for usage patterns like suspend2.

Well, I think that might only be useful for "temporary" flags, because if such a structure were to stay in memory permanently, it would be better to expand struct page anyway.

Quoted 5 lines

The other (suspend2 specific) advantage is that having them stored like this makes storing the image data much simpler and while we're calculating the contents of the image, there is zero impact on the size of this metadata storage from changes in the pages that are in each pagedir.

Quoted 4 lines

The question is if there are any potential users of this, except for suspend2. If not, it probably would make sense to use a more suspend2-specific and maybe simpler data structure and give up the generality.

Well, from a suspend2 perspective it's ideal, because saving the flags is just a case of iterating over the pages in the bitmap (yeah, and adding some metadata). If they were real pageflags, it would be much more painful.

If we were going to make this suspend2 only, all I'd do would be move dyn_pageflags.h and dyn_pageflags.c to kernel/power, combining them with pageflags.c and .h. I'm satisfied that the data structure is simple enough. It will cope with memory hot plugging and so on (maybe need some tweaking, but I haven't considered that yet). I do accept your argument that the code could do with some optimisation though.

Quoted 7 lines
Quoted 7 lines
Quoted 6 lines

Well, having read the entire patch I think I'd do this in a different way. Namely, we can always use pfn_to_page() to get the struct page corresponding to given PFN, so we can enumerate pages from 0 to max_pfn and create a simple bitmap with one or more bits per PFN. The only difficulty I see wrt this is to make sure 0-order allocations are used for the bitmaps.

Quoted 5 lines
Quoted 2 lines

I used to do that, but it arm pfns don't start at zero and it would leave gaps/wastage in the discontig mem case.

Would that be a big problem? That is, how many bits we would waste eg. on ARM?

I'm not sure, but it was enough to cause a concern to the guy who was working on an arm port earlier in the year. The other thing that might be relevant here is the amount of memory available. ARM is usually embedded, right?

Quoted 36 lines
Quoted 36 lines
Quoted 35 lines
Quoted 23 lines
 include/linux/dyn_pageflags.h |   66 ++++++++
 lib/Kconfig                   |    3
 lib/Makefile                  |    2
 lib/dyn_pageflags.c           |  330

+++++++++++++++++++++++++++++++++++++++++ 4 files changed, 401 insertions(+), 0 deletions(-)

(quoted diff) +0 -0

b/include/linux/dyn_pageflags.h new file mode 100644 index 0000000..1a7b5d8

include/linux/dyn_pageflags.h new file +8 -0
@@ -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

include/linux/dyn_pageflags.h line 18

Quoted 10 lines
include/linux/dyn_pageflags.h new file +10 -0
+ * 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;

Is this really necessary to define the dyn_pageflags_t here?

Quoted 5 lines
Quoted 3 lines

This will also be used in Suspend2's kernel/power/pageflags.c, which adds support for saving the pageflags in the image header and reloading and relocating them at resume time.

I would probably use unsigned long *** directly anyway.

Using the typedef has helped in debugging (it's quite possible to get confused when you start passing pointers to the locations of pageflags around). I'd really prefer to keep it.

Quoted 179 lines
Quoted 7 lines
Quoted 5 lines

include/linux/dyn_pageflags.h line 20

Quoted 2 lines
include/linux/dyn_pageflags.h new file +2 -0
+
+#define BITNUMBER(page) (page_to_pfn(page))

I think it would be cleaner to use page_to_pfn(page) verbatim instead of this.

I was going for readability.

Well, if I see BITNUMBER(page), I tend to check what it means, so I have to browse the code just to find out it's page_to_pfn(page). Ouch.

Quoted 40 lines
Quoted 18 lines
Quoted 18 lines
include/linux/dyn_pageflags.h new file +18 -0
+
+#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) >>
Quoted 8 lines
Quoted 5 lines

UL_SHIFT) +#define PAGEBIT(zone_offset) (zone_offset & BIT_NUM_MASK)

include/linux/dyn_pageflags.h new file +3 -0
+
+#define PAGE_UL_PTR(bitmap, zone_num, zone_pfn) \
+      

((bitmap[zone_num][PAGENUMBER(zone_pfn)])+PAGEINDEX(zone_pfn))

All of the above definitions seem to be related in an opaque way. Any chance to make them a bit more clearer? A comment, maybe?

Ok.

Quoted 10 lines
Quoted 7 lines
include/linux/dyn_pageflags.h new file +6 -0
+
+/* 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)) +*/

I'd choose different names for these. Also the definitions shouldn't go before test/set/clear_dynpageflag() are defined, IMO.

Quoted 2 lines

I was seeking to make them similar to the real pageflags semantics. Did you notice that this is a comment?

I didn't, sorry. Anyway it's a bit confusing.

Quoted 1 line

Will rearrange anyway.

OK

Quoted 95 lines
Quoted 86 lines
Quoted 86 lines
include/linux/dyn_pageflags.h new file +14 -0
+
+#define BITMAP_FOR_EACH_SET(bitmap, counter) \
+	for (counter = get_next_bit_on(bitmap, -1); counter > -1; \
+		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 void 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

lib/Kconfig +3 -0
index 3de9335..5596bd8 100644
@@ -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
 #
lib/Makefile +2 -0
index b830c9a..8290e9b 100644
@@ -31,6 +31,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
lib/dyn_pageflags.c new file +24 -0
new file mode 100644
index 0000000..4da52f5
@@ -0,0 +1,330 @@
+/*
+ * lib/dyn_pageflags.c
+ *
+ * Copyright (C) 2004-2006 Nigel Cunningham <[email protected]>
+ *
+ * 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) +

lib/dyn_pageflags.c new file +11 -0
+/*
+ * num_zones
+ *
+ * How many zones are there?
+ *
+ */
+
+static int num_zones(void)
+{
+	int result = 0;
+	struct zone *zone;
Quoted 8 lines

lib/dyn_pageflags.c line 42

Quoted 6 lines
lib/dyn_pageflags.c new file +6 -0
+
+	for_each_zone(zone)
+		result++;
+
+	return result;
+}

Do we really need this?

Quoted 4 lines

Well, I need to know how many zones there are, and haven't seen a generic function. If you know of one, please point me to it. (Or I could shift this somewhere else and make it a generic function - I'm aware that I have something similar in pageflags.c).

I don't know such a function, but if you need to call the above more than once it's plain inefficient. I'd define a variable num_zones instead.

Quoted 16 lines
Quoted 15 lines

lib/dyn_pageflags.c line 55

Quoted 13 lines
lib/dyn_pageflags.c new file +13 -0
+
+/*
+ * 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);
+}

Could you please explain the maths above?

Quoted 5 lines
Quoted 3 lines

Sure. Page_size << 3 is the number of bits in a page. We are calculating the number of pages needed to store spanned_pages bits, which is (spanned_pages + bits_per_page - 1) / (bits_per_page - 1). (Rounds up).

Any chance to use DIV_ROUND_UP here?

Wasn't aware of it's existence. Thanks.

Quoted 340 lines
Quoted 27 lines
Quoted 18 lines
Quoted 18 lines
lib/dyn_pageflags.c new file +18 -0
+
+/*
+ * 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++;
Quoted 8 lines

lib/dyn_pageflags.c line 79

Quoted 6 lines
lib/dyn_pageflags.c new file +6 -0
+
+	printk("Was looking for a zone for page %p.\n", page);
+	BUG_ON(1);
+
+	return 0;
+}

Why can't we use page_zonenum() instead of this?

Quoted 3 lines

They will only be the same thing in the x86 case. If you have multiple zones and some don't have any dma pages or highmem pages, this will give a more compact numbering.

But this is _really_ inefficient, because you call it for every page and for how many times? I think it should be fixed.

Quoted 65 lines
Quoted 11 lines
Quoted 11 lines
lib/dyn_pageflags.c new file +11 -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;
Quoted 8 lines

lib/dyn_pageflags.c line 96

Quoted 6 lines
lib/dyn_pageflags.c new file +6 -0
+
+	for_each_zone(zone)
+		total += pages_for_zone(zone);
+
+	return total;
+}

Why is a separate function needed for this?

Readability. Actually, answering this made me check again, and I couldn't find a user of this function. I'll remove it.

Quoted 33 lines
Quoted 11 lines
lib/dyn_pageflags.c new file +11 -0
+
+/*
+ * 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;

lib/dyn_pageflags.c line 117

Quoted 10 lines
lib/dyn_pageflags.c new file +10 -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++;
+	}
+}

I think this could be done in a simpler way too.

Quoted 9 lines
lib/dyn_pageflags.c new file +9 -0
+
+/*
+ * allocate_dyn_pageflags(dyn_pageflags_t *pagemap)
+ *
+ * Allocate a bitmap for dynamic page flags.
+ *
+ */
+int allocate_dyn_pageflags(dyn_pageflags_t *pagemap)
+{
Quoted 8 lines

lib/dyn_pageflags.c line 132

Quoted 6 lines
lib/dyn_pageflags.c new file +6 -0
+	int i, zone_num = 0;
+	struct zone *zone;
+
+	BUG_ON(*pagemap);
+
+	*pagemap = kmalloc(sizeof(void *) * num_zones(), GFP_ATOMIC);

By using kmalloc(), you use slab. I'd rather allocate entire pages.

Quoted 3 lines

You might only be using 20 bytes out of the page. At resume time, I do use entire pages if the kmalloc'd value needs relocating, but only if that's needed.

Which is not exactly straightforward. IMHO that should be simplified somehow.

Quoted 78 lines
Quoted 7 lines
Quoted 7 lines
lib/dyn_pageflags.c new file +7 -0
+
+	if (!*pagemap)
+		return -ENOMEM;
+
+	for_each_zone(zone) {
+		int zone_pages = pages_for_zone(zone);
+		(*pagemap)[zone_num] = kmalloc(sizeof(void *) * zone_pages,
Quoted 8 lines

lib/dyn_pageflags.c line 143

Quoted 4 lines
lib/dyn_pageflags.c new file +4 -0
+					       GFP_ATOMIC);
+
+		if (!(*pagemap)[zone_num]) {
+			kfree (*pagemap);

This seems to leak memory, eg. if *pagemap[0] is allocated, but the allocation of *pagemap[1] fails. You should free *pagemap[j] up to zone_num-1 and then *pagemap, IMO.

Yes, I should. Thanks.

Quoted 51 lines
Quoted 51 lines
lib/dyn_pageflags.c new file +23 -0
+			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.
+ *
+ */

lib/dyn_pageflags.c new file +23 -0
+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++;
Quoted 8 lines

lib/dyn_pageflags.c line 200

Quoted 6 lines
lib/dyn_pageflags.c new file +6 -0
+	}
+
+	if (PageSlab(virt_to_page((*pagemap))))
+		kfree(*pagemap);
+	else
+		free_page((unsigned long) (*pagemap));

Why so?

Quoted 1 line

See above (Suspend2 relocation at resume time).

Oh well ...

Quoted 24 lines
Quoted 15 lines
Quoted 15 lines
lib/dyn_pageflags.c new file +9 -0
+
+	*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.
+ *
+ */

lib/dyn_pageflags.c new file +2 -0
+
+unsigned long *dyn_pageflags_ul_ptr(dyn_pageflags_t *bitmap, struct

page *pg) +{

Quoted 8 lines

lib/dyn_pageflags.c line 221

Quoted 6 lines
lib/dyn_pageflags.c new file +6 -0
+	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;
+}

It doesn't look very efficient, does it? ;-)

Quoted 1 line

Readability again. I'm assuming the compiler is semi intelligent :)

Well, how is it supposed to optimise out the call to page_zone_number()? Also I wouldn't bet on the efficiency of the displacement computations.

Moreover, it would be nice to avoid calling page_to_zone_offset(page) for the second time in test/set/clear_dynpageflag below.

Quoted 120 lines
Quoted 95 lines
Quoted 95 lines
lib/dyn_pageflags.c new file +77 -0
+
+/*
+ * 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 -1.
+ *
+ */
+
+int get_next_bit_on(dyn_pageflags_t bitmap, int counter)
+{
+	struct page *page;
+	struct zone *zone;
+	unsigned long *ul = NULL;
+	int zone_offset, pagebit, zone_num, first;
+
+	first = (counter == -1);
+
+	if (first)
+		counter = first_online_pgdat()->node_zones->zone_start_pfn;
+
+	page = pfn_to_page(counter);
+	zone = page_zone(page);
+	zone_num = page_zone_number(page);
+	zone_offset = counter - zone->zone_start_pfn;
+
+	if (first) {
+		counter--;
+		zone_offset--;
+	} else
+		ul = (bitmap[zone_num][PAGENUMBER(zone_offset)]) +

PAGEINDEX(zone_offset); +

lib/dyn_pageflags.c new file +17 -0
+	do {
+		counter++;
+		zone_offset++;
+
+		if (zone_offset >= zone->spanned_pages) {
+			do {
+				zone = next_zone(zone);
+				if (!zone)
+					return -1;
+				zone_num++;
+			} while(!zone->spanned_pages);
+
+			counter = zone->zone_start_pfn;
+			zone_offset = 0;
+		}
+
+		/*
Quoted 8 lines

lib/dyn_pageflags.c line 320

Quoted 4 lines
lib/dyn_pageflags.c new file +4 -0
+		 * This could be optimised, but there are more
+		 * important things and the code is simple at
+		 * the moment
+		 */

Please let me disagree with this comment. I think it would be more efficient if you searched the bitmap for the first zero bit and then find the page, pfn, whatever corresponding to this bit.

Yes, it would be more efficient. I don't mind modifying it. This is a different moment to the one when I wrote that :)

Quoted 10 lines

lib/dyn_pageflags.c line 330

Quoted 10 lines
lib/dyn_pageflags.c new file +4 -0
+		pagebit = PAGEBIT(zone_offset);
+
+		if (!pagebit)
+			ul = (bitmap[zone_num][PAGENUMBER(zone_offset)]) +

PAGEINDEX(zone_offset); +

lib/dyn_pageflags.c new file +5 -0
+	} while(!test_bit(pagebit, ul));
+
+	return counter;
+}
+

Once again,

Quoted 6 lines
Quoted 3 lines

Thanks for your feedback. It's good to get picked up on cleanups I've missed and be made to remember again and provide the justification for decisions I've made.

Well, unfortunately the patch doesn't look very good to me. The overall idea is quite reasonable, but IMHO the implementation needs fixing.

Ok. I'll do some work on this. Thanks for your comments.

Regards,

Nigel

Signature · 2 lines
See http://www.suspend2.net for Howtos, FAQs, mailing
lists, wiki and bugzilla info.
#6 lore raw

Re: [Suspend2][] [Suspend2] Dynamically allocated pageflags

In reply to Rafael J. Wysocki

Hi.

Quoted 7 lines · Rafael J. Wysocki
Quoted 7 lines
Quoted 6 lines

Well, having read the entire patch I think I'd do this in a different way. Namely, we can always use pfn_to_page() to get the struct page corresponding to given PFN, so we can enumerate pages from 0 to max_pfn and create a simple bitmap with one or more bits per PFN. The only difficulty I see wrt this is to make sure 0-order allocations are used for the bitmaps.

Quoted 5 lines
Quoted 2 lines

I used to do that, but it arm pfns don't start at zero and it would leave gaps/wastage in the discontig mem case.

Would that be a big problem? That is, how many bits we would waste eg. on ARM?

It depends on the board (PHYS_PFN_OFFSET), but can be as much as 0xf0000000 (based on a quick search of include/asm-arm.

Quoted 10 lines
Quoted 7 lines
Quoted 5 lines

Review

Quoted 2 lines
(quoted diff) +2 -0
+
+#define BITNUMBER(page) (page_to_pfn(page))

I think it would be cleaner to use page_to_pfn(page) verbatim instead of this.

I was going for readability.

Well, if I see BITNUMBER(page), I tend to check what it means, so I have to browse the code just to find out it's page_to_pfn(page). Ouch.

Heh. It turned out to be another missed cleanup (was unused), so it's gone now.

Quoted 16 lines
Quoted 16 lines
Quoted 15 lines

lib/dyn_pageflags.c line 55

Quoted 13 lines
lib/dyn_pageflags.c new file +13 -0
+
+/*
+ * 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);
+}

Could you please explain the maths above?

Quoted 5 lines
Quoted 3 lines

Sure. Page_size << 3 is the number of bits in a page. We are calculating the number of pages needed to store spanned_pages bits, which is (spanned_pages + bits_per_page - 1) / (bits_per_page - 1). (Rounds up).

Any chance to use DIV_ROUND_UP here?

Where did you get that name from? I did find -name '*.[ch]' | xargs grep DIV_ROUND_UP and couldn't find it anywhere. Is it an -mm thing? If so, I'll keep an eye out for it getting mainlined.

Quoted 27 lines
Quoted 27 lines
Quoted 26 lines
Quoted 14 lines
lib/dyn_pageflags.c new file +14 -0
+
+/*
+ * 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)

lib/dyn_pageflags.c line 79

Quoted 10 lines
lib/dyn_pageflags.c new file +10 -0
+		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;
+}

Why can't we use page_zonenum() instead of this?

Quoted 6 lines
Quoted 3 lines

They will only be the same thing in the x86 case. If you have multiple zones and some don't have any dma pages or highmem pages, this will give a more compact numbering.

But this is _really_ inefficient, because you call it for every page and for how many times? I think it should be fixed.

It's called once each for set/test/clearing bits, and once for each get_next_bit_on. So far as I recall, every time I use these flags, I iterate through the whole lot. I can see that it would be more efficient to remember the number and only update it when we know we've gone to a new zone (as get_next_bit_on does when searching), but that would require passing the zone number back and forward to the caller, and this is probably not as bad as it looks anyway because its a small routine and the data will be reasonably likely (depending on what else the caller is doing) to still be in the cpu caches.

Quoted 18 lines
Quoted 18 lines
Quoted 17 lines
Quoted 5 lines
lib/dyn_pageflags.c new file +5 -0
+
+/*
+ * allocate_dyn_pageflags(dyn_pageflags_t *pagemap)
+ *
+ * Allocate a bitmap for dynamic page flags.

lib/dyn_pageflags.c line 132

Quoted 10 lines
lib/dyn_pageflags.c new file +10 -0
+ *
+ */
+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);

By using kmalloc(), you use slab. I'd rather allocate entire pages.

Quoted 6 lines
Quoted 3 lines

You might only be using 20 bytes out of the page. At resume time, I do use entire pages if the kmalloc'd value needs relocating, but only if that's needed.

Which is not exactly straightforward. IMHO that should be simplified somehow.

Do you have a concrete suggestion. I can't see how it can get simpler - everything I consider would be to make it more complicated.

Quoted 2 lines

Moreover, it would be nice to avoid calling page_to_zone_offset(page) for the second time in test/set/clear_dynpageflag below.

Fixed. I inlined dyn_pageflags_ul_ptr in each of the following functions and tidied.

Quoted 6 lines
Quoted 6 lines
Quoted 3 lines

Please let me disagree with this comment. I think it would be more efficient if you searched the bitmap for the first zero bit and then find the page, pfn, whatever corresponding to this bit.

Yes, it would be more efficient. I don't mind modifying it. This is a different moment to the one when I wrote that :)

Optimisation added.

Quoted 8 lines
Quoted 5 lines

Once again,

Thanks for your feedback. It's good to get picked up on cleanups I've missed and be made to remember again and provide the justification for decisions I've made.

Well, unfortunately the patch doesn't look very good to me. The overall idea is quite reasonable, but IMHO the implementation needs fixing.

Here's the new dyn_pageflags.c...

Regards,

Nigel

/*
* lib/dyn_pageflags.c
*
* Copyright (C) 2004-2006 Nigel Cunningham <[email protected]> *
* This file is released under the GPLv2.
*
* Routines for dynamically allocating and releasing bitmaps
* used as pseudo-pageflags.
*/

#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)

/*
* 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 *) * zones_in_use, 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]) {
			free_dyn_pageflags(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;
}

/*
* 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)

{
	int zone_pfn = page_to_zone_offset(page);
	int zone_num = page_zone_number(page);
	int pagenum = PAGENUMBER(zone_pfn);
	int page_offset = PAGEINDEX(zone_pfn);
	unsigned long *ul = ((*bitmap)[zone_num][pagenum]) + page_offset;
	int bit = PAGEBIT(zone_pfn);
	
	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)

{
	int zone_pfn = page_to_zone_offset(page);
	int zone_num = page_zone_number(page);
	int pagenum = PAGENUMBER(zone_pfn);
	int page_offset = PAGEINDEX(zone_pfn);
	unsigned long *ul = ((*bitmap)[zone_num][pagenum]) + page_offset;
	int bit = PAGEBIT(zone_pfn);
	
	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)

{
	int zone_pfn = page_to_zone_offset(page);
	int zone_num = page_zone_number(page);
	int pagenum = PAGENUMBER(zone_pfn);
	int page_offset = PAGEINDEX(zone_pfn);
	unsigned long *ul = ((*bitmap)[zone_num][pagenum]) + page_offset;
	int bit = PAGEBIT(zone_pfn);
	
	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 -1.
*
*/

int get_next_bit_on(dyn_pageflags_t bitmap, int counter)

{
	struct page *page;
	struct zone *zone;
	unsigned long *ul = NULL;
	int zone_offset, pagebit, zone_num, first;

	first = (counter == -1);
	
	if (first)
		counter = first_online_pgdat()->node_zones->zone_start_pfn;

	page = pfn_to_page(counter);
	zone = page_zone(page);
	zone_num = page_zone_number(page);
	zone_offset = counter - zone->zone_start_pfn;

	if (first) {
		counter--;
		zone_offset--;
	}

	do {
		counter++;
		zone_offset++;
	
		if (zone_offset >= zone->spanned_pages) {
			do {
				zone = next_zone(zone);
				if (!zone)
					return -1;
				zone_num++;
			} while(!zone->spanned_pages);

			counter = zone->zone_start_pfn;
			zone_offset = 0;
		}

		pagebit = PAGEBIT(zone_offset);

		if (!pagebit || !ul)
			ul = (bitmap[zone_num][PAGENUMBER(zone_offset)]) + PAGEINDEX(zone_offset);

		if (!(*ul & ~((1 << pagebit) - 1))) {
			int increment = BITS_PER_LONG - pagebit - 1;
			counter += increment;
			zone_offset += increment;
			continue;
		}

	} while(!test_bit(pagebit, ul));

	return counter;
}
Signature · 2 lines
See http://www.suspend2.net for Howtos, FAQs, mailing
lists, wiki and bugzilla info.
#7 lore raw

Re: [Suspend2][] [Suspend2] Dynamically allocated pageflags

Hi,

Quoted 8 lines · Nigel Cunningham
Quoted 7 lines · Rafael J. Wysocki
Quoted 7 lines
Quoted 6 lines

Well, having read the entire patch I think I'd do this in a different way. Namely, we can always use pfn_to_page() to get the struct page corresponding to given PFN, so we can enumerate pages from 0 to max_pfn and create a simple bitmap with one or more bits per PFN. The only difficulty I see wrt this is to make sure 0-order allocations are used for the bitmaps.

Quoted 8 lines
Quoted 5 lines
Quoted 2 lines

I used to do that, but it arm pfns don't start at zero and it would leave gaps/wastage in the discontig mem case.

Would that be a big problem? That is, how many bits we would waste eg. on ARM?

It depends on the board (PHYS_PFN_OFFSET), but can be as much as 0xf0000000 (based on a quick search of include/asm-arm.

That's quilte a lot. Actually the case in which PFNs don't start from 0 would be fixable, memory holes seem to be worse.

Quoted 33 lines
Quoted 10 lines
Quoted 7 lines
Quoted 5 lines

Review

Quoted 2 lines
(quoted diff) +2 -0
+
+#define BITNUMBER(page) (page_to_pfn(page))

I think it would be cleaner to use page_to_pfn(page) verbatim instead of this.

I was going for readability.

Well, if I see BITNUMBER(page), I tend to check what it means, so I have to browse the code just to find out it's page_to_pfn(page). Ouch.

Heh. It turned out to be another missed cleanup (was unused), so it's gone now.

Quoted 20 lines
Quoted 19 lines
Quoted 7 lines
Quoted 7 lines
lib/dyn_pageflags.c new file +7 -0
+
+/*
+ * pages_for_zone(struct zone *zone)
+ *
+ * How many pages do we need for a bitmap for this zone?
+ *
+ */
Quoted 8 lines

lib/dyn_pageflags.c line 55

Quoted 6 lines
lib/dyn_pageflags.c new file +6 -0
+
+static int pages_for_zone(struct zone *zone)
+{
+	return (zone->spanned_pages + (PAGE_SIZE << 3) - 1) >>
+			(PAGE_SHIFT + 3);
+}

Could you please explain the maths above?

Sure. Page_size << 3 is the number of bits in a page. We are calculating the number of pages needed to store spanned_pages bits, which is (spanned_pages + bits_per_page - 1) / (bits_per_page - 1). (Rounds up).

Quoted 5 lines
Quoted 1 line

Any chance to use DIV_ROUND_UP here?

Where did you get that name from? I did find -name '*.[ch]' | xargs grep DIV_ROUND_UP and couldn't find it anywhere. Is it an -mm thing? If so, I'll keep an eye out for it getting mainlined.

Sorry for that. I'm sure I used it at some time, but apparently it's gone now.

Quoted 35 lines
Quoted 28 lines
Quoted 28 lines
Quoted 27 lines
Quoted 15 lines
lib/dyn_pageflags.c new file +14 -0
+
+/*
+ * 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)

lib/dyn_pageflags.c line 79

Quoted 10 lines
lib/dyn_pageflags.c new file +10 -0
+		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;
+}

Why can't we use page_zonenum() instead of this?

Quoted 6 lines
Quoted 3 lines

They will only be the same thing in the x86 case. If you have multiple zones and some don't have any dma pages or highmem pages, this will give a more compact numbering.

But this is _really_ inefficient, because you call it for every page and for how many times? I think it should be fixed.

Quoted 8 lines

It's called once each for set/test/clearing bits, and once for each get_next_bit_on. So far as I recall, every time I use these flags, I iterate through the whole lot. I can see that it would be more efficient to remember the number and only update it when we know we've gone to a new zone (as get_next_bit_on does when searching), but that would require passing the zone number back and forward to the caller, and this is probably not as bad as it looks anyway because its a small routine and the data will be reasonably likely (depending on what else the caller is doing) to still be in the cpu caches.

Well, how about using the observation that
(page->flags >> ZONETABLE_PGSHIFT) & ZONETABLE_MASK
is an index in zone_table[] and enumerating zones using these indices? This is used by page_zone() to get the pointer to the page's struct zone, so it should be suitable for you too.

Quoted 22 lines
Quoted 22 lines
Quoted 21 lines
Quoted 9 lines
Quoted 9 lines
lib/dyn_pageflags.c new file +9 -0
+
+/*
+ * allocate_dyn_pageflags(dyn_pageflags_t *pagemap)
+ *
+ * Allocate a bitmap for dynamic page flags.
+ *
+ */
+int allocate_dyn_pageflags(dyn_pageflags_t *pagemap)
+{
Quoted 8 lines

lib/dyn_pageflags.c line 132

Quoted 6 lines
lib/dyn_pageflags.c new file +6 -0
+	int i, zone_num = 0;
+	struct zone *zone;
+
+	BUG_ON(*pagemap);
+
+	*pagemap = kmalloc(sizeof(void *) * num_zones(), GFP_ATOMIC);

By using kmalloc(), you use slab. I'd rather allocate entire pages.

You might only be using 20 bytes out of the page. At resume time, I do use entire pages if the kmalloc'd value needs relocating, but only if that's needed.

Quoted 5 lines
Quoted 2 lines

Which is not exactly straightforward. IMHO that should be simplified somehow.

Do you have a concrete suggestion. I can't see how it can get simpler - everything I consider would be to make it more complicated.

If you allocated a whole page in the beginning it wouldn't be so, I think. Even if you take only 20 bytes out of this page, it's temporary storage and your kmalloc() may result in a whole page being allocated as well.

Quoted 16 lines
Quoted 2 lines

Moreover, it would be nice to avoid calling page_to_zone_offset(page) for the second time in test/set/clear_dynpageflag below.

Fixed. I inlined dyn_pageflags_ul_ptr in each of the following functions and tidied.

Quoted 6 lines
Quoted 6 lines
Quoted 3 lines

Please let me disagree with this comment. I think it would be more efficient if you searched the bitmap for the first zero bit and then find the page, pfn, whatever corresponding to this bit.

Yes, it would be more efficient. I don't mind modifying it. This is a different moment to the one when I wrote that :)

Optimisation added.

Quoted 2 lines
Quoted 2 lines

Once again,

Quoted 8 lines
Quoted 6 lines
Quoted 3 lines

Thanks for your feedback. It's good to get picked up on cleanups I've missed and be made to remember again and provide the justification for decisions I've made.

Well, unfortunately the patch doesn't look very good to me. The overall idea is quite reasonable, but IMHO the implementation needs fixing.

Here's the new dyn_pageflags.c...

I'm too tired to look at it now, so probably I'll do that tomorrow. Also I'd like to see where you use this and how exactly. Could you please point me to that code?

Rafael