Skip to contentSkip to conversation

Dynamically allocated pageflags.

RFC PATCH In review Nigel Cunningham 3 participants 11 messages Jul 23, 2007 – Jul 24, 2007

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

cover Dynamically allocated pageflags.

Hi all.

As we all know, pageflags have been a scarce resource for a while now. These patches seek to help address that issue by adding support for a new type of 'dynamically allocated' pageflag.

The basic idea is that we use per node & zone bitmaps built out of order zero allocations, to replace bits in page->flags. Bitmaps can be sparse, being populated when a bit on the page is set, and returning zero for all bits in sparse pages. Untested hotplug support is included.

This method of storing the data does of course come with a performance hit. I've included some simple timing loops in #ifdef'd code that help quantify that.

Interestingly, the new implementation is actually quicker under some circumstances. In cases where the usage pattern involves operating on the flags for a number of pages in succession, the hit involved in getting the struct pages from main memory appears to be greater than that involved in calculating which unsigned long and bit to test.

Tested only on UP (x86_64) so far.

Regards,

Nigel

#1 lore raw

RFC PATCH 2/5 Dynamically allocated pageflags - PageMappedToDisk conversion.

Switch the "MappedToDisk" pageflag to using dynpageflags.

 include/linux/page-flags.h |    9 +++++----
 mm/dyn_pageflags.c         |    2 ++
 mm/page_alloc.c            |    3 ++-
 3 files changed, 9 insertions(+), 5 deletions(-)
include/linux/page-flags.h +5 -4
diff -ruNp 920-mapped-to-disk-pageflag.patch-old/include/linux/page-flags.h 920-mapped-to-disk-pageflag.patch-new/include/linux/page-flags.h
@@ -7,6 +7,7 @@
 
 #include <linux/types.h>
 #include <linux/mm_types.h>
+#include <linux/dyn_pageflags.h>
 
 /*
  * Various page->flags bits:
@@ -86,7 +87,6 @@
 #define PG_compound		14	/* Part of a compound page */
 #define PG_swapcache		15	/* Swap page: swp_entry_t in private */
 
-#define PG_mappedtodisk		16	/* Has blocks allocated on-disk */
 #define PG_reclaim		17	/* To be reclaimed asap */
 #define PG_buddy		19	/* Page is free, on buddy lists */
 
@@ -217,9 +217,10 @@ static inline void SetPageUptodate(struc
 #define __SetPageBuddy(page)	__set_bit(PG_buddy, &(page)->flags)
 #define __ClearPageBuddy(page)	__clear_bit(PG_buddy, &(page)->flags)
 
-#define PageMappedToDisk(page)	test_bit(PG_mappedtodisk, &(page)->flags)
-#define SetPageMappedToDisk(page) set_bit(PG_mappedtodisk, &(page)->flags)
-#define ClearPageMappedToDisk(page) clear_bit(PG_mappedtodisk, &(page)->flags)
+extern struct dyn_pageflags dyn_MappedToDisk_map;
+#define PageMappedToDisk(page)	test_dynpageflag(&dyn_MappedToDisk_map, page)
+#define SetPageMappedToDisk(page)	set_dynpageflag(&dyn_MappedToDisk_map, page)
+#define ClearPageMappedToDisk(page)	clear_dynpageflag(&dyn_MappedToDisk_map, page)
 
 #define PageReclaim(page)	test_bit(PG_reclaim, &(page)->flags)
 #define SetPageReclaim(page)	set_bit(PG_reclaim, &(page)->flags)
mm/dyn_pageflags.c +2 -0
diff -ruNp 920-mapped-to-disk-pageflag.patch-old/mm/dyn_pageflags.c 920-mapped-to-disk-pageflag.patch-new/mm/dyn_pageflags.c
@@ -113,6 +113,8 @@ static int dyn_pageflags_debug = 0;
 	for_each_online_pgdat(pgdat) \
 		for (zone_nr = 0; zone_nr < MAX_NR_ZONES; zone_nr++)
 
+DECLARE_DYN_PAGEFLAGS(dyn_MappedToDisk_map);
+
 /**
  * dump_pagemap: Display the contents of a bitmap for debugging purposes.
  *
mm/page_alloc.c +2 -1
diff -ruNp 920-mapped-to-disk-pageflag.patch-old/mm/page_alloc.c 920-mapped-to-disk-pageflag.patch-new/mm/page_alloc.c
@@ -610,7 +610,8 @@ static int prep_new_page(struct page *pa
 
 	page->flags &= ~(1 << PG_uptodate | 1 << PG_error |
 			1 << PG_referenced | 1 << PG_arch_1 |
-			1 << PG_owner_priv_1 | 1 << PG_mappedtodisk);
+			1 << PG_owner_priv_1);
+	ClearPageMappedToDisk(page);
 	set_page_private(page, 0);
 	set_page_refcounted(page);
 
#2 lore raw

RFC PATCH 3/5 Dynamically allocated pageflags - PageSwapCache conversion.

In reply to Nigel Cunningham

Switch PageSwapCache flag to use dynamically allocated pageflags.

 include/linux/page-flags.h |    7 ++++---
 mm/dyn_pageflags.c         |    3 +++
 2 files changed, 7 insertions(+), 3 deletions(-)
include/linux/page-flags.h +4 -3
diff -ruNp 921-page-swap-cache-pageflag.patch-old/include/linux/page-flags.h 921-page-swap-cache-pageflag.patch-new/include/linux/page-flags.h
@@ -260,9 +260,10 @@ static inline void __ClearPageTail(struc
 #define __ClearPageHead(page)	__ClearPageCompound(page)
 
 #ifdef CONFIG_SWAP
-#define PageSwapCache(page)	test_bit(PG_swapcache, &(page)->flags)
-#define SetPageSwapCache(page)	set_bit(PG_swapcache, &(page)->flags)
-#define ClearPageSwapCache(page) clear_bit(PG_swapcache, &(page)->flags)
+extern struct dyn_pageflags dyn_SwapCache_map;
+#define PageSwapCache(page)	test_dynpageflag(&dyn_SwapCache_map, page)
+#define SetPageSwapCache(page)	set_dynpageflag(&dyn_SwapCache_map, page)
+#define ClearPageSwapCache(page)	clear_dynpageflag(&dyn_SwapCache_map, page)
 #else
 #define PageSwapCache(page)	0
 #endif
mm/dyn_pageflags.c +3 -0
diff -ruNp 921-page-swap-cache-pageflag.patch-old/mm/dyn_pageflags.c 921-page-swap-cache-pageflag.patch-new/mm/dyn_pageflags.c
@@ -114,6 +114,9 @@ static int dyn_pageflags_debug = 0;
 		for (zone_nr = 0; zone_nr < MAX_NR_ZONES; zone_nr++)
 
 DECLARE_DYN_PAGEFLAGS(dyn_MappedToDisk_map);
+#ifdef CONFIG_SWAP
+DECLARE_DYN_PAGEFLAGS(dyn_SwapCache_map);
+#endif
 
 /**
  * dump_pagemap: Display the contents of a bitmap for debugging purposes.
#3 lore raw

RFC PATCH 4/5 Dynamically allocated pageflags - PageSlab conversion.

In reply to Nigel Cunningham

Convert PageSlab to use dynamically allocated page flags.

I'm not sure that we'll actually want to apply this, but it does work (I'm using it as I type this).

 include/linux/page-flags.h |    8 ++++----
 mm/dyn_pageflags.c         |    4 ++++
 mm/page_alloc.c            |    6 +++---
 mm/slub.c                  |    2 +-
 4 files changed, 12 insertions(+), 8 deletions(-)
include/linux/page-flags.h +4 -4
diff -ruNp 922-page-slab-pageflag.patch-old/include/linux/page-flags.h 922-page-slab-pageflag.patch-new/include/linux/page-flags.h
@@ -76,7 +76,6 @@
 #define PG_dirty	 	 4
 #define PG_lru			 5
 #define PG_active		 6
-#define PG_slab			 7	/* slab debug (Suparna wants this) */
 
 #define PG_owner_priv_1		 8	/* Owner use. If pagecache, fs may use*/
 #define PG_arch_1		 9
@@ -156,9 +155,10 @@ static inline void SetPageUptodate(struc
 #define ClearPageActive(page)	clear_bit(PG_active, &(page)->flags)
 #define __ClearPageActive(page)	__clear_bit(PG_active, &(page)->flags)
 
-#define PageSlab(page)		test_bit(PG_slab, &(page)->flags)
-#define __SetPageSlab(page)	__set_bit(PG_slab, &(page)->flags)
-#define __ClearPageSlab(page)	__clear_bit(PG_slab, &(page)->flags)
+extern struct dyn_pageflags dyn_Slab_map;
+#define PageSlab(page)	test_dynpageflag(&dyn_Slab_map, page)
+#define __SetPageSlab(page)	set_dynpageflag(&dyn_Slab_map, page)
+#define __ClearPageSlab(page)	clear_dynpageflag(&dyn_Slab_map, page)
 
 #ifdef CONFIG_HIGHMEM
 #define PageHighMem(page)	is_highmem(page_zone(page))
mm/dyn_pageflags.c +4 -0
diff -ruNp 922-page-slab-pageflag.patch-old/mm/dyn_pageflags.c 922-page-slab-pageflag.patch-new/mm/dyn_pageflags.c
@@ -114,6 +114,7 @@ static int dyn_pageflags_debug = 0;
 		for (zone_nr = 0; zone_nr < MAX_NR_ZONES; zone_nr++)
 
 DECLARE_DYN_PAGEFLAGS(dyn_MappedToDisk_map);
+DECLARE_DYN_PAGEFLAGS(dyn_Slab_map);
 #ifdef CONFIG_SWAP
 DECLARE_DYN_PAGEFLAGS(dyn_SwapCache_map);
 #endif
@@ -242,6 +243,9 @@ static void *normal_allocator(unsigned l
 void __init dyn_pageflags_init(void)
 {
 	dyn_allocator = boot_time_allocator;
+
+	/* Allocate the slab map early and not sparse. */
+	BUG_ON(allocate_dyn_pageflags(&dyn_Slab_map, 0));
 }
 
 /**
mm/page_alloc.c +3 -3
diff -ruNp 922-page-slab-pageflag.patch-old/mm/page_alloc.c 922-page-slab-pageflag.patch-new/mm/page_alloc.c
@@ -203,10 +203,10 @@ static void bad_page(struct page *page)
 			1 << PG_active	|
 			1 << PG_dirty	|
 			1 << PG_reclaim |
-			1 << PG_slab    |
 			1 << PG_swapcache |
 			1 << PG_writeback |
 			1 << PG_buddy );
+	__ClearPageSlab(page);
 	set_page_count(page, 0);
 	reset_page_mapcount(page);
 	page->mapping = NULL;
@@ -433,12 +433,12 @@ static inline int free_pages_check(struc
 	if (unlikely(page_mapcount(page) |
 		(page->mapping != NULL)  |
 		(page_count(page) != 0)  |
+		(PageSlab(page))	 |
 		(page->flags & (
 			1 << PG_lru	|
 			1 << PG_private |
 			1 << PG_locked	|
 			1 << PG_active	|
-			1 << PG_slab	|
 			1 << PG_swapcache |
 			1 << PG_writeback |
 			1 << PG_reserved |
@@ -587,6 +587,7 @@ static int prep_new_page(struct page *pa
 	if (unlikely(page_mapcount(page) |
 		(page->mapping != NULL)  |
 		(page_count(page) != 0)  |
+		(PageSlab(page))	 |
 		(page->flags & (
 			1 << PG_lru	|
 			1 << PG_private	|
@@ -594,7 +595,6 @@ static int prep_new_page(struct page *pa
 			1 << PG_active	|
 			1 << PG_dirty	|
 			1 << PG_reclaim	|
-			1 << PG_slab    |
 			1 << PG_swapcache |
 			1 << PG_writeback |
 			1 << PG_reserved |
mm/slub.c +1 -1
diff -ruNp 922-page-slab-pageflag.patch-old/mm/slub.c 922-page-slab-pageflag.patch-new/mm/slub.c
@@ -1032,7 +1032,7 @@ static struct page *new_slab(struct kmem
 		atomic_long_inc(&n->nr_slabs);
 	page->offset = s->offset / sizeof(void *);
 	page->slab = s;
-	page->flags |= 1 << PG_slab;
+	__SetPageSlab(page);
 	if (s->flags & (SLAB_DEBUG_FREE | SLAB_RED_ZONE | SLAB_POISON |
 			SLAB_STORE_USER | SLAB_TRACE))
 		SetSlabDebug(page);
#4 lore raw

RFC PATCH 5/5 Dynamically allocated pageflags - PageBuddy conversion.

In reply to Nigel Cunningham

Convert PageBuddy to dynamically allocate pageflags.

Again, not sure that we'd actually want to apply this, but it demonstrates that the implementation is usable.

 include/linux/page-flags.h |    8 ++++----
 mm/dyn_pageflags.c         |    2 ++
 mm/page_alloc.c            |   12 ++++++------
 3 files changed, 12 insertions(+), 10 deletions(-)
include/linux/page-flags.h +4 -4
diff -ruNp 923-page-buddy-pageflags.patch-old/include/linux/page-flags.h 923-page-buddy-pageflags.patch-new/include/linux/page-flags.h
@@ -87,7 +87,6 @@
 #define PG_swapcache		15	/* Swap page: swp_entry_t in private */
 
 #define PG_reclaim		17	/* To be reclaimed asap */
-#define PG_buddy		19	/* Page is free, on buddy lists */
 
 /* PG_owner_priv_1 users should have descriptive aliases */
 #define PG_checked		PG_owner_priv_1 /* Used by some filesystems */
@@ -213,9 +212,10 @@ extern struct dyn_pageflags dyn_Slab_map
 		ret;							\
 	})
 
-#define PageBuddy(page)		test_bit(PG_buddy, &(page)->flags)
-#define __SetPageBuddy(page)	__set_bit(PG_buddy, &(page)->flags)
-#define __ClearPageBuddy(page)	__clear_bit(PG_buddy, &(page)->flags)
+extern struct dyn_pageflags dyn_Buddy_map;
+#define PageBuddy(page)	test_dynpageflag(&dyn_Buddy_map, page)
+#define __SetPageBuddy(page)	set_dynpageflag(&dyn_Buddy_map, page)
+#define __ClearPageBuddy(page)	clear_dynpageflag(&dyn_Buddy_map, page)
 
 extern struct dyn_pageflags dyn_MappedToDisk_map;
 #define PageMappedToDisk(page)	test_dynpageflag(&dyn_MappedToDisk_map, page)
mm/dyn_pageflags.c +2 -0
diff -ruNp 923-page-buddy-pageflags.patch-old/mm/dyn_pageflags.c 923-page-buddy-pageflags.patch-new/mm/dyn_pageflags.c
@@ -115,6 +115,7 @@ static int dyn_pageflags_debug = 0;
 
 DECLARE_DYN_PAGEFLAGS(dyn_MappedToDisk_map);
 DECLARE_DYN_PAGEFLAGS(dyn_Slab_map);
+DECLARE_DYN_PAGEFLAGS(dyn_Buddy_map);
 #ifdef CONFIG_SWAP
 DECLARE_DYN_PAGEFLAGS(dyn_SwapCache_map);
 #endif
@@ -246,6 +247,7 @@ void __init dyn_pageflags_init(void)
 
 	/* Allocate the slab map early and not sparse. */
 	BUG_ON(allocate_dyn_pageflags(&dyn_Slab_map, 0));
+	BUG_ON(allocate_dyn_pageflags(&dyn_Buddy_map, 0));
 }
 
 /**
mm/page_alloc.c +6 -6
diff -ruNp 923-page-buddy-pageflags.patch-old/mm/page_alloc.c 923-page-buddy-pageflags.patch-new/mm/page_alloc.c
@@ -204,9 +204,9 @@ static void bad_page(struct page *page)
 			1 << PG_dirty	|
 			1 << PG_reclaim |
 			1 << PG_swapcache |
-			1 << PG_writeback |
-			1 << PG_buddy );
+			1 << PG_writeback);
 	__ClearPageSlab(page);
+	__ClearPageBuddy(page);
 	set_page_count(page, 0);
 	reset_page_mapcount(page);
 	page->mapping = NULL;
@@ -434,6 +434,7 @@ static inline int free_pages_check(struc
 		(page->mapping != NULL)  |
 		(page_count(page) != 0)  |
 		(PageSlab(page))	 |
+		(PageBuddy(page))	 |
 		(page->flags & (
 			1 << PG_lru	|
 			1 << PG_private |
@@ -441,8 +442,7 @@ static inline int free_pages_check(struc
 			1 << PG_active	|
 			1 << PG_swapcache |
 			1 << PG_writeback |
-			1 << PG_reserved |
-			1 << PG_buddy ))))
+			1 << PG_reserved))))
 		bad_page(page);
 	/*
 	 * PageReclaim == PageTail. It is only an error
@@ -588,6 +588,7 @@ static int prep_new_page(struct page *pa
 		(page->mapping != NULL)  |
 		(page_count(page) != 0)  |
 		(PageSlab(page))	 |
+		(PageBuddy(page))	 |
 		(page->flags & (
 			1 << PG_lru	|
 			1 << PG_private	|
@@ -597,8 +598,7 @@ static int prep_new_page(struct page *pa
 			1 << PG_reclaim	|
 			1 << PG_swapcache |
 			1 << PG_writeback |
-			1 << PG_reserved |
-			1 << PG_buddy ))))
+			1 << PG_reserved))))
 		bad_page(page);
 
 	/*
#5 lore raw
In reply to Nigel Cunningham

Bah.

Sorry for sending it twice. Fun with figuring out Kmail encoding.

Anyway, I forgot to include the stats in the previous message. Here they are.

[   20.667431] Dynpageflags testing...
[   20.667433] Set page 1...Ok.
[   20.667440] Test memory hotplugging #1 ...Ok.
[   20.667442] Test memory hotplugging #2 ...Ok.
[   21.935293] input: AT Translated Set 2 keyboard as /class/input/input1
[   22.188954] Dyn: 98 iterations of setting & clearing all 253935 flags took 152 jiffies.
[   24.584302] Real flags: 98 iterations of setting & clearing all 253935 flags took 240 jiffies.
[   25.644460] Dyn: 25000000 iterations of setting & clearing all one flag took 106 jiffies.
[   25.797906] Real pageflag: 25000000 iterations of setting & clearing all one flag took 15 jiffies.

Nigel

#6 lore raw
In reply to Nigel Cunningham
Quoted 5 lines · Nigel Cunningham

Hi all.

As we all know, pageflags have been a scarce resource for a while now. These patches seek to help address that issue by adding support for a new type of 'dynamically allocated' pageflag.

but... does this really solve it? I mean.. you can still run out... so then what?

#7 lore raw

Hi.

Quoted 4 lines · On Tuesday 24 July 2007 00:29:55 Arjan van de Ven wrote:
Quoted 3 lines · Nigel Cunningham

Hi all.

As we all know, pageflags have been a scarce resource for a while now.

These

Quoted 6 lines
Quoted 2 lines

patches seek to help address that issue by adding support for a new type of 'dynamically allocated' pageflag.

but... does this really solve it? I mean.. you can still run out... so then what?

Well, the intention is that you can use this implementation instead for flags where the performance hit doesn't matter [so much].

Regards,

Nigel

Signature · 2 lines
See http://www.tuxonice.net for Howtos, FAQs, mailing
lists, wiki and bugzilla info.
#8 lore raw
In reply to Nigel Cunningham

Hi,

Quoted 15 lines · Nigel Cunningham

Hi all.

As we all know, pageflags have been a scarce resource for a while now. These patches seek to help address that issue by adding support for a new type of 'dynamically allocated' pageflag.

The basic idea is that we use per node & zone bitmaps built out of order zero allocations, to replace bits in page->flags. Bitmaps can be sparse, being populated when a bit on the page is set, and returning zero for all bits in sparse pages. Untested hotplug support is included.

This method of storing the data does of course come with a performance hit. I've included some simple timing loops in #ifdef'd code that help quantify that.

Quoted 7 lines

Interestingly, the new implementation is actually quicker under some circumstances. In cases where the usage pattern involves operating on the flags for a number of pages in succession, the hit involved in getting the struct pages from main memory appears to be greater than that involved in calculating which unsigned long and bit to test.

Tested only on UP (x86_64) so far.

How does it compare to the memory bitmaps used by swsusp, defined in kernel/power/snapshot.c?

Greetings,
Rafael

Signature · 1 line
"Premature optimization is the root of all evil." - Donald Knuth
#9 lore raw

Hi.

Quoted 6 lines · On Tuesday 24 July 2007 08:05:21 Rafael J. Wysocki wrote:

Hi,

Quoted 3 lines · Nigel Cunningham

Hi all.

As we all know, pageflags have been a scarce resource for a while now.

These

Quoted 4 lines
Quoted 4 lines

patches seek to help address that issue by adding support for a new type of 'dynamically allocated' pageflag.

The basic idea is that we use per node & zone bitmaps built out of order

zero

Quoted 2 lines
Quoted 2 lines

allocations, to replace bits in page->flags. Bitmaps can be sparse, being populated when a bit on the page is set, and returning zero for all bits

in

Quoted 3 lines
Quoted 3 lines

sparse pages. Untested hotplug support is included.

This method of storing the data does of course come with a performance

hit.

Quoted 9 lines
Quoted 9 lines

I've included some simple timing loops in #ifdef'd code that help quantify that.

Interestingly, the new implementation is actually quicker under some circumstances. In cases where the usage pattern involves operating on the flags for a number of pages in succession, the hit involved in getting the struct pages from main memory appears to be greater than that involved in calculating which unsigned long and bit to test.

Quoted 4 lines
Quoted 1 line

Tested only on UP (x86_64) so far.

How does it compare to the memory bitmaps used by swsusp, defined in kernel/power/snapshot.c?

Looking through kernel/power/snapshot.c, I'd say this implementation has advantages in having support for memory hotplugging, sparseness and random access to the flags in the bitmap. Like the snapshot.c implementation, it uses per-zone bitmaps and has a method that can be used to iterate over the contents of a bitmap. Having per-node support might also be useful. I haven't looked at the speed of the snapshot.c implementation. Do you see advantages to snapshot.c that I might have missed?

Regards,

Nigel

Signature · 2 lines
See http://www.tuxonice.net for Howtos, FAQs, mailing
lists, wiki and bugzilla info.
#10 lore raw
Quoted 36 lines · Nigel Cunningham

Hi.

Quoted 6 lines · On Tuesday 24 July 2007 08:05:21 Rafael J. Wysocki wrote:

Hi,

Quoted 3 lines · Nigel Cunningham

Hi all.

As we all know, pageflags have been a scarce resource for a while now.

These

Quoted 4 lines
Quoted 4 lines

patches seek to help address that issue by adding support for a new type of 'dynamically allocated' pageflag.

The basic idea is that we use per node & zone bitmaps built out of order

zero

Quoted 2 lines
Quoted 2 lines

allocations, to replace bits in page->flags. Bitmaps can be sparse, being populated when a bit on the page is set, and returning zero for all bits

in

Quoted 3 lines
Quoted 3 lines

sparse pages. Untested hotplug support is included.

This method of storing the data does of course come with a performance

hit.

Quoted 9 lines
Quoted 9 lines

I've included some simple timing loops in #ifdef'd code that help quantify that.

Interestingly, the new implementation is actually quicker under some circumstances. In cases where the usage pattern involves operating on the flags for a number of pages in succession, the hit involved in getting the struct pages from main memory appears to be greater than that involved in calculating which unsigned long and bit to test.

Quoted 4 lines
Quoted 1 line

Tested only on UP (x86_64) so far.

How does it compare to the memory bitmaps used by swsusp, defined in kernel/power/snapshot.c?

Quoted 6 lines

Looking through kernel/power/snapshot.c, I'd say this implementation has advantages in having support for memory hotplugging, sparseness and random access to the flags in the bitmap. Like the snapshot.c implementation, it uses per-zone bitmaps and has a method that can be used to iterate over the contents of a bitmap. Having per-node support might also be useful. I haven't looked at the speed of the snapshot.c implementation.

Well, that's what I'm really interested in.

Quoted 1 line

Do you see advantages to snapshot.c that I might have missed?

Not at the moment, but I need to have a closer look.

Greetings,
Rafael

Signature · 1 line
"Premature optimization is the root of all evil." - Donald Knuth