Skip to contentSkip to conversation

Make page->private usable in compound pages V1

PATCH In review Christoph Lameter 2 participants 19 messages Apr 5, 2007 – Apr 9, 2007

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

PATCH 1/2 Make page->private usable in compound pages V1

[PATCH] Free up page->private for compound pages

If we add a new flag so that we can distinguish between the first page and the tail pages then we can avoid to use page->private in the first page. page->private == page for the first page, so there is no real information in there.

Freeing up page->private makes the use of compound pages more transparent. They become more usable like real pages. Right now we have to be careful f.e. if we are going beyond PAGE_SIZE allocations in the slab on i386 because we can then no longer use the private field. This is one of the issues that cause us not to support debugging for page size slabs in SLAB.

Having page->private available for SLUB would allow more meta information in the page struct. I can probably avoid the 16 bit ints that I have in there right now.

Also if page->private is available then a compound page may be equipped with buffer heads. This may free up the way for filesystems to support larger blocks than page size.

We add PageTail as an alias of PageReclaim. Compound pages cannot currently be reclaimed. Because of the alias one needs to check PageCompound first.

The RFC for the this approach was discussed at
http://marc.info/?t=117574302800001&r=1&w=2

include/linux/mm.h +28 -5
Index: linux-2.6.21-rc5-mm4/include/linux/mm.h
===================================================================
@@ -297,17 +297,28 @@ static inline int get_page_unless_zero(s
 	return atomic_inc_not_zero(&page->_count);
 }
 
+static inline struct page *compound_head(struct page *page)
+{
+	/*
+	 * We could avoid the PageCompound(page) check if
+	 * we would not overload PageTail().
+	 *
+	 * This check has to be done in several performance critical
+	 * paths of the slab etc. IMHO PageTail deserves its own flag.
+	 */
+	if (unlikely(PageCompound(page) && PageTail(page)))
+		return page->first_page;
+	return page;
+}
+
 static inline int page_count(struct page *page)
 {
-	if (unlikely(PageCompound(page)))
-		page = (struct page *)page_private(page);
-	return atomic_read(&page->_count);
+	return atomic_read(&compound_head(page)->_count);
 }
 
 static inline void get_page(struct page *page)
 {
-	if (unlikely(PageCompound(page)))
-		page = (struct page *)page_private(page);
+	page = compound_head(page);
 	VM_BUG_ON(atomic_read(&page->_count) == 0);
 	atomic_inc(&page->_count);
 }
@@ -344,6 +355,18 @@ static inline compound_page_dtor *get_co
 	return (compound_page_dtor *)page[1].lru.next;
 }
 
+static inline int compound_order(struct page *page)
+{
+	if (!PageCompound(page) || PageTail(page))
+		return 0;
+	return (unsigned long)page[1].lru.prev;
+}
+
+static inline void set_compound_order(struct page *page, unsigned long order)
+{
+	page[1].lru.prev = (void *)order;
+}
+
 /*
  * Multiple processes may "see" the same page. E.g. for untouched
  * mappings of /dev/null, all processes see the same page full of
include/linux/page-flags.h +14 -0
Index: linux-2.6.21-rc5-mm4/include/linux/page-flags.h
===================================================================
@@ -95,6 +95,12 @@
 /* PG_owner_priv_1 users should have descriptive aliases */
 #define PG_checked		PG_owner_priv_1 /* Used by some filesystems */
 
+/*
+ * Marks tail portion of a compound page. We currently do not reclaim
+ * compound pages so we can reuse a flag only used for reclaim here.
+ */
+#define PG_tail			PG_reclaim
+
 #if (BITS_PER_LONG > 32)
 /*
  * 64-bit-only flags build down from bit 31
@@ -214,6 +220,14 @@ static inline void SetPageUptodate(struc
 #define __SetPageCompound(page)	__set_bit(PG_compound, &(page)->flags)
 #define __ClearPageCompound(page) __clear_bit(PG_compound, &(page)->flags)
 
+/*
+ * Note: PG_tail is an alias of another page flag. The result of PageTail()
+ * is only valid if PageCompound(page) is true.
+ */
+#define PageTail(page)	test_bit(PG_tail, &(page)->flags)
+#define __SetPageTail(page)	__set_bit(PG_tail, &(page)->flags)
+#define __ClearPageTail(page)	__clear_bit(PG_tail, &(page)->flags)
+
 #ifdef CONFIG_SWAP
 #define PageSwapCache(page)	test_bit(PG_swapcache, &(page)->flags)
 #define SetPageSwapCache(page)	set_bit(PG_swapcache, &(page)->flags)
mm/internal.h +1 -1
Index: linux-2.6.21-rc5-mm4/mm/internal.h
===================================================================
@@ -24,7 +24,7 @@ static inline void set_page_count(struct
  */
 static inline void set_page_refcounted(struct page *page)
 {
-	VM_BUG_ON(PageCompound(page) && page_private(page) != (unsigned long)page);
+	VM_BUG_ON(PageCompound(page) && PageTail(page));
 	VM_BUG_ON(atomic_read(&page->_count));
 	set_page_count(page, 1);
 }
mm/page_alloc.c +20 -9
Index: linux-2.6.21-rc5-mm4/mm/page_alloc.c
===================================================================
@@ -290,7 +290,7 @@ static void bad_page(struct page *page)
 
 static void free_compound_page(struct page *page)
 {
-	__free_pages_ok(page, (unsigned long)page[1].lru.prev);
+	__free_pages_ok(page, compound_order(page));
 }
 
 static void prep_compound_page(struct page *page, unsigned long order)
@@ -299,12 +299,14 @@ static void prep_compound_page(struct pa
 	int nr_pages = 1 << order;
 
 	set_compound_page_dtor(page, free_compound_page);
-	page[1].lru.prev = (void *)order;
-	for (i = 0; i < nr_pages; i++) {
+	set_compound_order(page, order);
+	__SetPageCompound(page);
+	for (i = 1; i < nr_pages; i++) {
 		struct page *p = page + i;
 
+		__SetPageTail(p);
 		__SetPageCompound(p);
-		set_page_private(p, (unsigned long)page);
+		p->first_page = page;
 	}
 }
 
@@ -313,15 +315,19 @@ static void destroy_compound_page(struct
 	int i;
 	int nr_pages = 1 << order;
 
-	if (unlikely((unsigned long)page[1].lru.prev != order))
+	if (unlikely(compound_order(page) != order))
 		bad_page(page);
 
-	for (i = 0; i < nr_pages; i++) {
+	if (unlikely(!PageCompound(page)))
+			bad_page(page);
+	__ClearPageCompound(page);
+	for (i = 1; i < nr_pages; i++) {
 		struct page *p = page + i;
 
-		if (unlikely(!PageCompound(p) |
-				(page_private(p) != (unsigned long)page)))
+		if (unlikely(!PageCompound(p) | !PageTail(p) |
+				(p->first_page != page)))
 			bad_page(page);
+		__ClearPageTail(p);
 		__ClearPageCompound(p);
 	}
 }
@@ -494,13 +500,18 @@ static inline int free_pages_check(struc
 			1 << PG_private |
 			1 << PG_locked	|
 			1 << PG_active	|
-			1 << PG_reclaim	|
 			1 << PG_slab	|
 			1 << PG_swapcache |
 			1 << PG_writeback |
 			1 << PG_reserved |
 			1 << PG_buddy ))))
 		bad_page(page);
+	/*
+	 * PageReclaim == PageTail. It is only an error
+	 * for PageReclaim to be set if PageCompound is clear.
+	 */
+	if (unlikely(!PageCompound(page) && PageReclaim(page)))
+		bad_page(page);
 	if (PageDirty(page))
 		__ClearPageDirty(page);
 	/*
mm/slab.c +2 -4
Index: linux-2.6.21-rc5-mm4/mm/slab.c
===================================================================
@@ -602,8 +602,7 @@ static inline void page_set_cache(struct
 
 static inline struct kmem_cache *page_get_cache(struct page *page)
 {
-	if (unlikely(PageCompound(page)))
-		page = (struct page *)page_private(page);
+	page = compound_head(page);
 	BUG_ON(!PageSlab(page));
 	return (struct kmem_cache *)page->lru.next;
 }
@@ -615,8 +614,7 @@ static inline void page_set_slab(struct 
 
 static inline struct slab *page_get_slab(struct page *page)
 {
-	if (unlikely(PageCompound(page)))
-		page = (struct page *)page_private(page);
+	page = compound_head(page);
 	BUG_ON(!PageSlab(page));
 	return (struct slab *)page->lru.prev;
 }
mm/slub.c +4 -15
Index: linux-2.6.21-rc5-mm4/mm/slub.c
===================================================================
@@ -1273,9 +1273,7 @@ void kmem_cache_free(struct kmem_cache *
 
 	page = virt_to_page(x);
 
-	if (unlikely(PageCompound(page)))
-		page = page->first_page;
-
+	page = compound_head(page);
 
 	if (unlikely(PageError(page) && (s->flags & SLAB_STORE_USER)))
 		set_tracking(s, x, 1);
@@ -1286,10 +1284,7 @@ EXPORT_SYMBOL(kmem_cache_free);
 /* Figure out on which slab object the object resides */
 static struct page *get_object_page(const void *x)
 {
-	struct page *page = virt_to_page(x);
-
-	if (unlikely(PageCompound(page)))
-		page = page->first_page;
+	struct page *page = compound_head(virt_to_page(x));
 
 	if (!PageSlab(page))
 		return NULL;
@@ -1896,10 +1891,7 @@ void kfree(const void *x)
 	if (!x)
 		return;
 
-	page = virt_to_page(x);
-
-	if (unlikely(PageCompound(page)))
-		page = page->first_page;
+	page = compound_head(virt_to_page(x));
 
 	s = page->slab;
 
@@ -1935,10 +1927,7 @@ void *krealloc(const void *p, size_t new
 		return NULL;
 	}
 
-	page = virt_to_page(p);
-
-	if (unlikely(PageCompound(page)))
-		page = page->first_page;
+	page = compound_head(virt_to_page(p));
 
 	new_cache = get_slab(new_size, flags);
 
mm/swap.c +1 -1
Index: linux-2.6.21-rc5-mm4/mm/swap.c
===================================================================
@@ -56,7 +56,7 @@ static void fastcall __page_cache_releas
 
 static void put_compound_page(struct page *page)
 {
-	page = (struct page *)page_private(page);
+	page = compound_head(page);
 	if (put_page_testzero(page)) {
 		compound_page_dtor *dtor;
 
arch/ia64/mm/init.c +1 -1
Index: linux-2.6.21-rc5-mm4/arch/ia64/mm/init.c
===================================================================
@@ -121,7 +121,7 @@ lazy_mmu_prot_update (pte_t pte)
 		return;				/* i-cache is already coherent with d-cache */
 
 	if (PageCompound(page)) {
-		order = (unsigned long) (page[1].lru.prev);
+		order = compound_order(page);
 		flush_icache_range(addr, addr + (1UL << order << PAGE_SHIFT));
 	}
 	else
#1 lore raw

PATCH 2/2 Optimize compound_head() by avoiding a shared page flag

Unalias PG_tail for performance reasons

If PG_tail is an alias then we need to check PageCompound before PageTail. This is particularly bad because the slab and others have to use these tests in performance critical paths.

This patch uses one of the freed up software suspend flags that is defined next to PG_compound.

Excerpt from kfree (page = compound_head(page)) before patch:

r33 = pointer to page struct.

0xa000000100170271 <kfree+49>:              ld4.acq r14=[r33]
0xa000000100170272 <kfree+50>:              nop.i 0x0;;
0xa000000100170280 <kfree+64>:  [MIB]       nop.m 0x0
0xa000000100170281 <kfree+65>:              tbit.z p9,p8=r14,14
0xa000000100170282 <kfree+66>:        (p09) br.cond.dptk.few 0xa0000001001702c0 <kfree+128>
0xa000000100170290 <kfree+80>:  [MMI]       ld4.acq r9=[r33]
0xa000000100170291 <kfree+81>:              nop.m 0x0
0xa000000100170292 <kfree+82>:              adds r8=16,r33;;
0xa0000001001702a0 <kfree+96>:  [MII]       nop.m 0x0
0xa0000001001702a1 <kfree+97>:              tbit.z p10,p11=r9,17
0xa0000001001702a2 <kfree+98>:              nop.i 0x0
0xa0000001001702b0 <kfree+112>: [MMI]       nop.m 0x0;;

0xa0000001001702b1 <kfree+113>: (p11) ld8 r33=[r8]
0xa0000001001702b2 <kfree+114>: nop.i 0x0;;
0xa0000001001702c0 <kfree+128>: [MII] ...

After patch:

r34 pointer to page struct

0xa00000010016f541 <kfree+65>:              ld4.acq r3=[r34]
0xa00000010016f542 <kfree+66>:              nop.i 0x0
0xa00000010016f550 <kfree+80>:  [MMI]       adds r2=16,r34;;
0xa00000010016f551 <kfree+81>:              nop.m 0x0
0xa00000010016f552 <kfree+82>:              tbit.z p10,p11=r3,13;;

0xa00000010016f560 <kfree+96>: [MII] (p11) ld8 r34=[r2]

No branch anymore.

include/linux/page-flags.h +1 -10
Index: linux-2.6.21-rc5-mm4/include/linux/page-flags.h
===================================================================
@@ -82,6 +82,7 @@
 #define PG_private		11	/* If pagecache, has fs-private data */
 
 #define PG_writeback		12	/* Page is under writeback */
+#define PG_tail			13	/* Page is tail of a compound page */
 #define PG_compound		14	/* Part of a compound page */
 #define PG_swapcache		15	/* Swap page: swp_entry_t in private */
 
@@ -95,12 +96,6 @@
 /* PG_owner_priv_1 users should have descriptive aliases */
 #define PG_checked		PG_owner_priv_1 /* Used by some filesystems */
 
-/*
- * Marks tail portion of a compound page. We currently do not reclaim
- * compound pages so we can reuse a flag only used for reclaim here.
- */
-#define PG_tail			PG_reclaim
-
 #if (BITS_PER_LONG > 32)
 /*
  * 64-bit-only flags build down from bit 31
@@ -220,10 +215,6 @@ static inline void SetPageUptodate(struc
 #define __SetPageCompound(page)	__set_bit(PG_compound, &(page)->flags)
 #define __ClearPageCompound(page) __clear_bit(PG_compound, &(page)->flags)
 
-/*
- * Note: PG_tail is an alias of another page flag. The result of PageTail()
- * is only valid if PageCompound(page) is true.
- */
 #define PageTail(page)	test_bit(PG_tail, &(page)->flags)
 #define __SetPageTail(page)	__set_bit(PG_tail, &(page)->flags)
 #define __ClearPageTail(page)	__clear_bit(PG_tail, &(page)->flags)
mm/page_alloc.c +1 -6
Index: linux-2.6.21-rc5-mm4/mm/page_alloc.c
===================================================================
@@ -500,18 +500,13 @@ static inline int free_pages_check(struc
 			1 << PG_private |
 			1 << PG_locked	|
 			1 << PG_active	|
+			1 << PG_reclaim |
 			1 << PG_slab	|
 			1 << PG_swapcache |
 			1 << PG_writeback |
 			1 << PG_reserved |
 			1 << PG_buddy ))))
 		bad_page(page);
-	/*
-	 * PageReclaim == PageTail. It is only an error
-	 * for PageReclaim to be set if PageCompound is clear.
-	 */
-	if (unlikely(!PageCompound(page) && PageReclaim(page)))
-		bad_page(page);
 	if (PageDirty(page))
 		__ClearPageDirty(page);
 	/*
mm/internal.h +1 -1
Index: linux-2.6.21-rc5-mm4/mm/internal.h
===================================================================
@@ -24,7 +24,7 @@ static inline void set_page_count(struct
  */
 static inline void set_page_refcounted(struct page *page)
 {
-	VM_BUG_ON(PageCompound(page) && PageTail(page));
+	VM_BUG_ON(PageTail(page));
 	VM_BUG_ON(atomic_read(&page->_count));
 	set_page_count(page, 1);
 }
include/linux/mm.h +1 -8
Index: linux-2.6.21-rc5-mm4/include/linux/mm.h
===================================================================
@@ -299,14 +299,7 @@ static inline int get_page_unless_zero(s
 
 static inline struct page *compound_head(struct page *page)
 {
-	/*
-	 * We could avoid the PageCompound(page) check if
-	 * we would not overload PageTail().
-	 *
-	 * This check has to be done in several performance critical
-	 * paths of the slab etc. IMHO PageTail deserves its own flag.
-	 */
-	if (unlikely(PageCompound(page) && PageTail(page)))
+	if (unlikely(PageTail(page)))
 		return page->first_page;
 	return page;
 }
maintainer
#2 lore raw

Re: [PATCH 2/2] Optimize compound_head() by avoiding a shared page flag

Quoted 8 lines · On Thu, 5 Apr 2007 15:36:57 -0700 (PDT) Christoph Lameter <[email protected]>…

Unalias PG_tail for performance reasons

If PG_tail is an alias then we need to check PageCompound before PageTail. This is particularly bad because the slab and others have to use these tests in performance critical paths.

This patch uses one of the freed up software suspend flags that is defined next to PG_compound.

I get a reject from this because it is dependent upon later patches. As the Official Protector Of Page Flags, I'm going to drop it.

Did you investigate

static inline int page_tail(struct page *page)

{
	return ((page->flags & (PG_compound|PG_tail)) == (PG_compound|PG_tail));
}

and

static inline int page_tail(struct page *page)

{
	return unlikely(PageCompound(page)) && unlikely(PageTail(page));
}

?

In the latter case we _should_ have a not-taken branch to not-inline code. If the compiler doesn't do that, we can make the PageTail() test an out-of-line function. Or make the whole thing an uninlined function.

More work needed, please. I don't expect that a not-taken branch to not-inline code is worth a new page flag. Especially as it does not actually reduce the number of branch decisions in the common case.

(I'm assuming in all of this that !PageCompound() is the very common case with slub. If that is not true, we need to talk).

#3 lore raw

Re: [PATCH 2/2] Optimize compound_head() by avoiding a shared page flag

Quoted 6 lines · Andrew Morton

Did you investigate

static inline int page_tail(struct page *page)

{
	return ((page->flags & (PG_compound|PG_tail)) == (PG_compound|PG_tail));
}

The usual test_bit that we are using there uses a volatile reference so these wont be combined if I check them separately.

A working example of the above would be much uglier:

static inline int page_tail(struct page *page)
{
return ((page->flags & ((1L << PG_compound)|(1L << PG_tail))) ==
((1L << PG_compound)|(1L << PG_tail)));
}

May be this can be cleaned up somehow.

Quoted 7 lines

and

static inline int page_tail(struct page *page)

{
	return unlikely(PageCompound(page)) && unlikely(PageTail(page));
}

Two volatile references in the bit opes that the compiler cannot combine. Wont work unless we clean up the bitops first. This means we still have two branches in the code. Maybe I can make the first one work.

Quoted 3 lines

In the latter case we _should_ have a not-taken branch to not-inline code. If the compiler doesn't do that, we can make the PageTail() test an out-of-line function. Or make the whole thing an uninlined function.

Still two branches which cannot be optimized in the same way as the single on on IA64 as shown by the asm that I included.

Quoted 3 lines

More work needed, please. I don't expect that a not-taken branch to not-inline code is worth a new page flag. Especially as it does not actually reduce the number of branch decisions in the common case.

A new page flag does reduce the number of branches. On several platforms it eliminates the branch completely since a single instruction can be conditionally skipped.

Quoted 2 lines

(I'm assuming in all of this that !PageCompound() is the very common case with slub. If that is not true, we need to talk).

Yes, it is common for slabs to only have a single page.

The most promising avenue seems to be the simultaneous check for two bits.

maintainer
#4 lore raw

Re: [PATCH 2/2] Optimize compound_head() by avoiding a shared page flag

Quoted 14 lines · On Sat, 7 Apr 2007 15:16:17 -0700 (PDT) Christoph Lameter <[email protected]>…
Quoted 6 lines · Andrew Morton

Did you investigate

static inline int page_tail(struct page *page)

{
	return ((page->flags & (PG_compound|PG_tail)) == (PG_compound|PG_tail));
}

The usual test_bit that we are using there uses a volatile reference so these wont be combined if I check them separately.

A working example of the above would be much uglier:

Quoted 7 lines

static inline int page_tail(struct page *page)
{
return ((page->flags & ((1L << PG_compound)|(1L << PG_tail))) ==
((1L << PG_compound)|(1L << PG_tail)));
}

May be this can be cleaned up somehow.

It might generate better code to do

	unsigned long compound;

	compound = page->flags & (1 << PG_compound);
	if (PG_compound > PG_tail)
		return compound & (page->flags << (PG_compound - PG_tail));
	else
		return compound & (page->flags << (PG_tail - PG_compound));

ie: get the PG_compound flag into compound', then bitwise-and that with the PG_tail flag, after shifting it into PG_compound' slot. The return value will be zero if either bit is clear, (1<<PG_compound) if both are set. The if (PG_compound > PG_tail)' will be swallowed by the compiler.

The compiler should turn it all into

	(page->flags & N) & (page->flags << M)

Which may or may not be better than (page->flags & N == N), dunno. Probably not - if the compiler's any good it won't save a branch, I suspect.

Which is all a ton of fun, but this subversion of the architecture's freedom to use volatile, memory barriers etc is a worry. We do the same in page_alloc.c, of course...

#5 lore raw

Re: [PATCH 2/2] Optimize compound_head() by avoiding a shared page flag

Quoted 3 lines · Andrew Morton

Which is all a ton of fun, but this subversion of the architecture's freedom to use volatile, memory barriers etc is a worry. We do the same in page_alloc.c, of course...

I just tried the approach that we discussed earlier and it was not nice either. Lets just use a page flag please. This check will be in several hot code paths. And it may become more important because the file system folks want to support buffers > page size. Then we may want more transparent support for huge pages... For all of this page->private gets in the way.

And I think we curently have 5 or so page flags available?

maintainer
#6 lore raw

Re: [PATCH 2/2] Optimize compound_head() by avoiding a shared page flag

Quoted 8 lines · On Sat, 7 Apr 2007 17:21:38 -0700 (PDT) Christoph Lameter <[email protected]>…
Quoted 3 lines · Andrew Morton

Which is all a ton of fun, but this subversion of the architecture's freedom to use volatile, memory barriers etc is a worry. We do the same in page_alloc.c, of course...

I just tried the approach that we discussed earlier and it was not nice either.

We've discussed at least three approaches, so we don't know to what you refer.

Quoted 1 line

Lets just use a page flag please.

Nope, try harder.

PageCompound is an unlikely case. Back in the old days we would have done

	if (PageCompound(page))
		goto out_of_line;

back:

	do_stuff_with(page);
	return;

out_of_line:

	if (PageTail(page)) {
		page = page_tail(page);
		goto back;
	}
	<do other stuff>

and nowadays we hope that gcc does the above for us. If it doesn't do it for us, perhaps it needs open-coded help.

Because I don't expect there will be much efficiency difference between the above and the use of another page flag.

#7 lore raw

Re: [PATCH 2/2] Optimize compound_head() by avoiding a shared page flag

Quoted 4 lines · Andrew Morton
Quoted 2 lines

I just tried the approach that we discussed earlier and it was not nice either.

We've discussed at least three approaches, so we don't know to what you refer.

Thats the approach of checking two flags at the same time. In that case the compiler will generate and "and-immediate" and then a "compare-immediate" one branch but .... Yuck.

Quoted 2 lines

Because I don't expect there will be much efficiency difference between the above and the use of another page flag.

Then we end up with all these small efficiency differences in all the code paths. I'd rather go for optimal performance in a frequently used construct like this.

This check is not rare. It is done on every SLAB free and on every get_page() and put_page(). Lets do the page flag.

maintainer
#8 lore raw

Re: [PATCH 2/2] Optimize compound_head() by avoiding a shared page flag

Quoted 10 lines · On Sat, 7 Apr 2007 18:32:04 -0700 (PDT) Christoph Lameter <[email protected]>…
Quoted 4 lines · Andrew Morton
Quoted 2 lines

I just tried the approach that we discussed earlier and it was not nice either.

We've discussed at least three approaches, so we don't know to what you refer.

Thats the approach of checking two flags at the same time. In that case the compiler will generate and "and-immediate" and then a "compare-immediate" one branch but .... Yuck.

Right.

        movl    (%ebx), %eax    # <variable>.flags, tmp399
        andl    $48, %eax       #, tmp399
        cmpl    $48, %eax       #, tmp399
        je      .L265   #,

what's "yuck" about that?

With the single page flag:

	movl	(%ebx), %eax	#* page.521, D.21940
	testb	$32, %al	#, D.21940
	jne	.L265	#,

So you're talking about saving one sole single silly solitary instruction.

Quoted 6 lines
Quoted 2 lines

Because I don't expect there will be much efficiency difference between the above and the use of another page flag.

Then we end up with all these small efficiency differences in all the code paths. I'd rather go for optimal performance in a frequently used construct like this.

You can save that worrisome single instruction in the common case by putting the handling of the uncommon compound pages out of line, as I indicated.

#9 lore raw

Re: [PATCH 2/2] Optimize compound_head() by avoiding a shared page flag

Quoted 8 lines · Andrew Morton
        andl    $48, %eax       #, tmp399
        cmpl    $48, %eax       #, tmp399
        je      .L265   #,

what's "yuck" about that?

Quoted 7 lines

With the single page flag:

	movl	(%ebx), %eax	#* page.521, D.21940
	testb	$32, %al	#, D.21940
	jne	.L265	#,

So you're talking about saving one sole single silly solitary instruction.

We are also using another register. The bit instructions can just go in an test. Ok. Will submit this patch. .... Maybe I can special case 64 bit.

#10 lore raw

Re: [PATCH 2/2] Optimize compound_head() by avoiding a shared page flag

In reply to Andrew Morton

Add PageTail / PageHead in order to avoid multiple branches when compound pages are checked.

The patch adds PageTail(page) and PageHead(page) to check if a page is the head or the tail of a compound page. This is done by masking the two bits describing the state of a compound page and then comparing them. So one comparision and a branch instead of two bit checks and two branches.

---
 include/linux/mm.h         |   11 ++---------
 include/linux/page-flags.h |   28 +++++++++++++++++-----------
 mm/page_alloc.c            |   10 ++++------
 3 files changed, 23 insertions(+), 26 deletions(-)
include/linux/mm.h +2 -9
Index: linux-2.6.21-rc5-mm4/include/linux/mm.h
===================================================================
@@ -299,14 +299,7 @@ static inline int get_page_unless_zero(s
 
 static inline struct page *compound_head(struct page *page)
 {
-	/*
-	 * We could avoid the PageCompound(page) check if
-	 * we would not overload PageTail().
-	 *
-	 * This check has to be done in several performance critical
-	 * paths of the slab etc. IMHO PageTail deserves its own flag.
-	 */
-	if (unlikely(PageCompound(page) && PageTail(page)))
+	if (unlikely(PageTail(page)))
 		return page->first_page;
 	return page;
 }
@@ -363,7 +356,7 @@ static inline compound_page_dtor *get_co
 
 static inline int compound_order(struct page *page)
 {
-	if (!PageCompound(page) || PageTail(page))
+	if (!PageHead(page))
 		return 0;
 	return (unsigned long)page[1].lru.prev;
 }
include/linux/page-flags.h +17 -11
Index: linux-2.6.21-rc5-mm4/include/linux/page-flags.h
===================================================================
@@ -95,12 +95,6 @@
 /* PG_owner_priv_1 users should have descriptive aliases */
 #define PG_checked		PG_owner_priv_1 /* Used by some filesystems */
 
-/*
- * Marks tail portion of a compound page. We currently do not reclaim
- * compound pages so we can reuse a flag only used for reclaim here.
- */
-#define PG_tail			PG_reclaim
-
 #if (BITS_PER_LONG > 32)
 /*
  * 64-bit-only flags build down from bit 31
@@ -221,12 +215,24 @@ static inline void SetPageUptodate(struc
 #define __ClearPageCompound(page) __clear_bit(PG_compound, &(page)->flags)
 
 /*
- * Note: PG_tail is an alias of another page flag. The result of PageTail()
- * is only valid if PageCompound(page) is true.
+ * PG_reclaim is used in combination with PG_compound to mark the
+ * head and tail of a compound page
+ *
+ * PG_compound & PG_reclaim	=> Tail page
+ * PG_compound & ~PG_reclaim	=> Head page
  */
-#define PageTail(page)	test_bit(PG_tail, &(page)->flags)
-#define __SetPageTail(page)	__set_bit(PG_tail, &(page)->flags)
-#define __ClearPageTail(page)	__clear_bit(PG_tail, &(page)->flags)
+
+#define PG_head_tail_mask ((1L << PG_compound) | (1L << PG_reclaim))
+
+#define PageTail(page)	((page->flags & PG_head_tail_mask) \
+				== PG_head_tail_mask)
+#define __SetPageTail(page)	page->flags |= PG_head_tail_mask
+#define __ClearPageTail(page)	page->flags ~= PG_head_tail_mask
+
+#define PageHead(page)	((page->flags & PG_head_tail_mask) \
+				== (1L << PG_compound))
+#define __SetPageHead(page)	__SetCompoundPage(page)
+#define __ClearPageHead(page)	__ClearCompoundPage(page)
 
 #ifdef CONFIG_SWAP
 #define PageSwapCache(page)	test_bit(PG_swapcache, &(page)->flags)
mm/page_alloc.c +4 -6
Index: linux-2.6.21-rc5-mm4/mm/page_alloc.c
===================================================================
@@ -300,12 +300,11 @@ static void prep_compound_page(struct pa
 
 	set_compound_page_dtor(page, free_compound_page);
 	set_compound_order(page, order);
-	__SetPageCompound(page);
+	__SetPageHead(page);
 	for (i = 1; i < nr_pages; i++) {
 		struct page *p = page + i;
 
 		__SetPageTail(p);
-		__SetPageCompound(p);
 		p->first_page = page;
 	}
 }
@@ -318,17 +317,16 @@ static void destroy_compound_page(struct
 	if (unlikely(compound_order(page) != order))
 		bad_page(page);
 
-	if (unlikely(!PageCompound(page)))
+	if (unlikely(!PageHead(page)))
 			bad_page(page);
-	__ClearPageCompound(page);
+	__ClearPageHead(page);
 	for (i = 1; i < nr_pages; i++) {
 		struct page *p = page + i;
 
-		if (unlikely(!PageCompound(p) | !PageTail(p) |
+		if (unlikely(!PageTail(p) |
 				(p->first_page != page)))
 			bad_page(page);
 		__ClearPageTail(p);
-		__ClearPageCompound(p);
 	}
 }
 
maintainer
#11 lore raw

Re: [PATCH 2/2] Optimize compound_head() by avoiding a shared page flag

Quoted 8 lines · On Mon, 9 Apr 2007 11:09:40 -0700 (PDT) Christoph Lameter <[email protected]>…

Add PageTail / PageHead in order to avoid multiple branches when compound pages are checked.

The patch adds PageTail(page) and PageHead(page) to check if a page is the head or the tail of a compound page. This is done by masking the two bits describing the state of a compound page and then comparing them. So one comparision and a branch instead of two bit checks and two branches.

OK. I'm still a bit concerned about bypassing the bitops synchronisation:
barriers, volatile, etc. We had lengthy ruminations on that a few years ago, I think when working on free_pages_check().

Quoted 12 lines
include/linux/page-flags.h +5 -2
@@ -221,12 +215,24 @@ static inline void SetPageUptodate(struc
 #define __ClearPageCompound(page) __clear_bit(PG_compound, &(page)->flags)
 
 /*
- * Note: PG_tail is an alias of another page flag. The result of PageTail()
- * is only valid if PageCompound(page) is true.
+ * PG_reclaim is used in combination with PG_compound to mark the
+ * head and tail of a compound page
+ *
+ * PG_compound & PG_reclaim	=> Tail page
+ * PG_compound & ~PG_reclaim	=> Head page
  */

include/linux/page-flags.h static inline void SetPageUptodate(struc · line 230

Quoted 10 lines
include/linux/page-flags.h +7 -3
-#define PageTail(page)	test_bit(PG_tail, &(page)->flags)
-#define __SetPageTail(page)	__set_bit(PG_tail, &(page)->flags)
-#define __ClearPageTail(page)	__clear_bit(PG_tail, &(page)->flags)
+
+#define PG_head_tail_mask ((1L << PG_compound) | (1L << PG_reclaim))
+
+#define PageTail(page)	((page->flags & PG_head_tail_mask) \
+				== PG_head_tail_mask)
+#define __SetPageTail(page)	page->flags |= PG_head_tail_mask
+#define __ClearPageTail(page)	page->flags ~= PG_head_tail_mask

hm. The lack of parenthesisation here _might_ be OK, but I haven't thought it through.

And I'd prefer not to have to, because I know that the do { } while (0) thing works. As do static inline functions.

include/linux/page-flags.h static inline void SetPageUptodate(struc · line 235

Quoted 4 lines
include/linux/page-flags.h +4 -0
+#define PageHead(page)	((page->flags & PG_head_tail_mask) \
+				== (1L << PG_compound))
+#define __SetPageHead(page)	__SetCompoundPage(page)
+#define __ClearPageHead(page)	__ClearCompoundPage(page)

You meant __SetPageCompound and __ClearPageCompound.

#12 lore raw

Re: [PATCH 2/2] Optimize compound_head() by avoiding a shared page flag

Quoted 9 lines · Andrew Morton
Quoted 5 lines

The patch adds PageTail(page) and PageHead(page) to check if a page is the head or the tail of a compound page. This is done by masking the two bits describing the state of a compound page and then comparing them. So one comparision and a branch instead of two bit checks and two branches.

OK. I'm still a bit concerned about bypassing the bitops synchronisation:
barriers, volatile, etc. We had lengthy ruminations on that a few years ago, I think when working on free_pages_check().

Those are important for bits that are changing while a page is in use. These are constant.

Quoted 5 lines

include/linux/page-flags.h static inline void SetPageUptodate(struc · line 230

Quoted 2 lines
include/linux/page-flags.h +2 -0
+#define __SetPageTail(page)	page->flags |= PG_head_tail_mask
+#define __ClearPageTail(page)	page->flags ~= PG_head_tail_mask

hm. The lack of parenthesisation here _might_ be OK, but I haven't thought it through.

This is a command and not an expression. Ok will inline.

Quoted 9 lines

And I'd prefer not to have to, because I know that the do { } while (0) thing works. As do static inline functions.

include/linux/page-flags.h static inline void SetPageUptodate(struc · line 235

Quoted 4 lines
include/linux/page-flags.h +4 -0
+#define PageHead(page)	((page->flags & PG_head_tail_mask) \
+				== (1L << PG_compound))
+#define __SetPageHead(page)	__SetCompoundPage(page)
+#define __ClearPageHead(page)	__ClearCompoundPage(page)

You meant __SetPageCompound and __ClearPageCompound.

Right.

#13 lore raw

Re: [PATCH 2/2] Optimize compound_head() by avoiding a shared page flag

In reply to Andrew Morton

Here is another rev on that one. Inlined the two functions but that required #including <mm_types.h>

Add PageTail / PageHead in order to avoid multiple branches when compound pages are checked.

The patch adds PageTail(page) and PageHead(page) to check if a page is the head or the tail of a compound page. This is done by masking the two bits describing the state of a compound page and then comparing them. So one comparision and a branch instead of two bit checks and two branches.

---
 include/linux/mm.h         |   11 ++---------
 include/linux/page-flags.h |   28 +++++++++++++++++-----------
 mm/page_alloc.c            |   10 ++++------
 3 files changed, 23 insertions(+), 26 deletions(-)
include/linux/mm.h +2 -9
Index: linux-2.6.21-rc6-mm1/include/linux/mm.h
===================================================================
@@ -299,14 +299,7 @@ static inline int get_page_unless_zero(s
 
 static inline struct page *compound_head(struct page *page)
 {
-	/*
-	 * We could avoid the PageCompound(page) check if
-	 * we would not overload PageTail().
-	 *
-	 * This check has to be done in several performance critical
-	 * paths of the slab etc. IMHO PageTail deserves its own flag.
-	 */
-	if (unlikely(PageCompound(page) && PageTail(page)))
+	if (unlikely(PageTail(page)))
 		return page->first_page;
 	return page;
 }
@@ -363,7 +356,7 @@ static inline compound_page_dtor *get_co
 
 static inline int compound_order(struct page *page)
 {
-	if (!PageCompound(page) || PageTail(page))
+	if (!PageHead(page))
 		return 0;
 	return (unsigned long)page[1].lru.prev;
 }
include/linux/page-flags.h +26 -11
Index: linux-2.6.21-rc6-mm1/include/linux/page-flags.h
===================================================================
@@ -6,6 +6,7 @@
 #define PAGE_FLAGS_H
 
 #include <linux/types.h>
+#include <linux/mm_types.h>
 
 /*
  * Various page->flags bits:
@@ -95,12 +96,6 @@
 /* PG_owner_priv_1 users should have descriptive aliases */
 #define PG_checked		PG_owner_priv_1 /* Used by some filesystems */
 
-/*
- * Marks tail portion of a compound page. We currently do not reclaim
- * compound pages so we can reuse a flag only used for reclaim here.
- */
-#define PG_tail			PG_reclaim
-
 #if (BITS_PER_LONG > 32)
 /*
  * 64-bit-only flags build down from bit 31
@@ -221,12 +216,32 @@ static inline void SetPageUptodate(struc
 #define __ClearPageCompound(page) __clear_bit(PG_compound, &(page)->flags)
 
 /*
- * Note: PG_tail is an alias of another page flag. The result of PageTail()
- * is only valid if PageCompound(page) is true.
+ * PG_reclaim is used in combination with PG_compound to mark the
+ * head and tail of a compound page
+ *
+ * PG_compound & PG_reclaim	=> Tail page
+ * PG_compound & ~PG_reclaim	=> Head page
  */
-#define PageTail(page)	test_bit(PG_tail, &(page)->flags)
-#define __SetPageTail(page)	__set_bit(PG_tail, &(page)->flags)
-#define __ClearPageTail(page)	__clear_bit(PG_tail, &(page)->flags)
+
+#define PG_head_tail_mask ((1L << PG_compound) | (1L << PG_reclaim))
+
+#define PageTail(page)	((page->flags & PG_head_tail_mask) \
+				== PG_head_tail_mask)
+
+static inline void __SetPageTail(struct page *page)
+{
+	page->flags |= PG_head_tail_mask;
+}
+
+static inline void __ClearPageTail(struct page *page)
+{
+	page->flags &= ~PG_head_tail_mask;
+}
+
+#define PageHead(page)	((page->flags & PG_head_tail_mask) \
+				== (1L << PG_compound))
+#define __SetPageHead(page)	__SetPageCompound(page)
+#define __ClearPageHead(page)	__ClearPageCompound(page)
 
 #ifdef CONFIG_SWAP
 #define PageSwapCache(page)	test_bit(PG_swapcache, &(page)->flags)
mm/page_alloc.c +4 -6
Index: linux-2.6.21-rc6-mm1/mm/page_alloc.c
===================================================================
@@ -300,12 +300,11 @@ static void prep_compound_page(struct pa
 
 	set_compound_page_dtor(page, free_compound_page);
 	set_compound_order(page, order);
-	__SetPageCompound(page);
+	__SetPageHead(page);
 	for (i = 1; i < nr_pages; i++) {
 		struct page *p = page + i;
 
 		__SetPageTail(p);
-		__SetPageCompound(p);
 		p->first_page = page;
 	}
 }
@@ -318,17 +317,16 @@ static void destroy_compound_page(struct
 	if (unlikely(compound_order(page) != order))
 		bad_page(page);
 
-	if (unlikely(!PageCompound(page)))
+	if (unlikely(!PageHead(page)))
 			bad_page(page);
-	__ClearPageCompound(page);
+	__ClearPageHead(page);
 	for (i = 1; i < nr_pages; i++) {
 		struct page *p = page + i;
 
-		if (unlikely(!PageCompound(p) | !PageTail(p) |
+		if (unlikely(!PageTail(p) |
 				(p->first_page != page)))
 			bad_page(page);
 		__ClearPageTail(p);
-		__ClearPageCompound(p);
 	}
 }
 
maintainer
#14 lore raw
In reply to Christoph Lameter
Quoted 15 lines · On Thu, 5 Apr 2007 15:36:51 -0700 (PDT) Christoph Lameter <[email protected]>…

If we add a new flag so that we can distinguish between the first page and the tail pages then we can avoid to use page->private in the first page. page->private == page for the first page, so there is no real information in there.

Freeing up page->private makes the use of compound pages more transparent. They become more usable like real pages. Right now we have to be careful f.e. if we are going beyond PAGE_SIZE allocations in the slab on i386 because we can then no longer use the private field. This is one of the issues that cause us not to support debugging for page size slabs in SLAB.

Having page->private available for SLUB would allow more meta information in the page struct. I can probably avoid the 16 bit ints that I have in there right now.

Quoted 7 lines

Also if page->private is available then a compound page may be equipped with buffer heads. This may free up the way for filesystems to support larger blocks than page size.

We add PageTail as an alias of PageReclaim. Compound pages cannot currently be reclaimed. Because of the alias one needs to check PageCompound first.

So slub is using compound pages so that it can locate the head page in higher-order pages, whereas slab uses per-object (or per-order-0-page?) metadata for that?

I see four instances of

+ page = virt_to_page(p);
+
+ if (unlikely(PageCompound(page)))
+ page = page->first_page;

A new virt_to_head_page() is needed.

Sigh. We're seeing rather a lot of churn to accommodate slub. Do we actually have any justification for all this? If we end up deciding to merge slub and to deprecate then remove slab, what would our reasons have been?

#15 lore raw
Quoted 7 lines · Andrew Morton
Quoted 3 lines

We add PageTail as an alias of PageReclaim. Compound pages cannot currently be reclaimed. Because of the alias one needs to check PageCompound first.

So slub is using compound pages so that it can locate the head page in higher-order pages, whereas slab uses per-object (or per-order-0-page?) metadata for that?

Both SLAB and SLUB use compound pages.

Quoted 9 lines

I see four instances of

(quoted diff) +4 -0
+	page = virt_to_page(p);
+
+	if (unlikely(PageCompound(page)))
+		page = page->first_page;

A new virt_to_head_page() is needed.

Ok.

Quoted 4 lines

Sigh. We're seeing rather a lot of churn to accommodate slub. Do we actually have any justification for all this? If we end up deciding to merge slub and to deprecate then remove slab, what would our reasons have been?

This is not SLUB specific. SLAB does the same. SLAB does special casing for page size slabs and does not allow slab debugging because it would use page->private if debugging would be enabled. Which would get into trouble on i386.

If you want less SLUB churn on other fronts then I can add the special casing for PAGE_SIZE slabs back into SLUB. Then we keep all the inconsistencies in SLAB use in the code.

I'd rather clean up the stuff and then also remove the special casing from SLAB.

maintainer
#16 lore raw
Quoted 11 lines · On Fri, 6 Apr 2007 10:01:38 -0700 (PDT) Christoph Lameter <[email protected]>…
Quoted 7 lines · Andrew Morton
Quoted 3 lines

We add PageTail as an alias of PageReclaim. Compound pages cannot currently be reclaimed. Because of the alias one needs to check PageCompound first.

So slub is using compound pages so that it can locate the head page in higher-order pages, whereas slab uses per-object (or per-order-0-page?) metadata for that?

Both SLAB and SLUB use compound pages.

Not really. slab sets the page->lru.prev of each constituent page to point at the controlling slab.

I assume the PageCompound() handling in (for example) page_get_cache() is for the NOMMU special case.

Quoted 22 lines
Quoted 9 lines

I see four instances of

(quoted diff) +4 -0
+	page = virt_to_page(p);
+
+	if (unlikely(PageCompound(page)))
+		page = page->first_page;

A new virt_to_head_page() is needed.

Ok.

Quoted 4 lines

Sigh. We're seeing rather a lot of churn to accommodate slub. Do we actually have any justification for all this? If we end up deciding to merge slub and to deprecate then remove slab, what would our reasons have been?

This is not SLUB specific. SLAB does the same. SLAB does special casing for page size slabs and does not allow slab debugging because it would use page->private if debugging would be enabled. Which would get into trouble on i386.

Quoted 7 lines

If you want less SLUB churn on other fronts then I can add the special casing for PAGE_SIZE slabs back into SLUB. Then we keep all the inconsistencies in SLAB use in the code.

I'd rather clean up the stuff and then also remove the special casing from SLAB.

Will slub handle NOMMU anonymous pages appropriately?

#17 lore raw
Quoted 4 lines · Andrew Morton
Quoted 1 line

Both SLAB and SLUB use compound pages.

Not really. slab sets the page->lru.prev of each constituent page to point at the controlling slab.

Uhh.. More slab inconsistencies. page[1]->lru is used for compound pages in the !MMU case.

Quoted 1 line

From page_alloc.c:

/*
* Higher-order pages are called "compound pages". They are structured
thusly:
*
* The first tail page's ->lru.next holds the address of the compound
page's
* put_page() function. Its ->lru.prev holds the order of allocation.
* This usage means that zero-order pages may not be compound. */

Quoted 1 line

Will slub handle NOMMU anonymous pages appropriately?

I am not sure how anonymous pages relate to the slab allocators.

SLUB consistently uses compound pages for all higher order allocations. And those are usually fine for mmu and no mmu even without this series of patches unless someone pokes around page->private.

#18 lore raw
In reply to Andrew Morton
Quoted 1 line · Andrew Morton

A new virt_to_head_page() is needed.

Add virt_to_head_page and consolidate code in slab and slub.

include/linux/mm.h +6 -0
Index: linux-2.6.21-rc5-mm4/include/linux/mm.h
===================================================================
@@ -316,6 +316,12 @@
 	atomic_inc(&page->_count);
 }
 
+static inline struct page *virt_to_head_page(const void *x)
+{
+	struct page *page = virt_to_page(x);
+	return compound_head(page);
+}
+
 /*
  * Setup the page count before being freed into the page allocator for
  * the first time (boot or memory hotplug)
mm/slab.c +4 -5
Index: linux-2.6.21-rc5-mm4/mm/slab.c
===================================================================
@@ -614,20 +614,19 @@
 
 static inline struct slab *page_get_slab(struct page *page)
 {
-	page = compound_head(page);
 	BUG_ON(!PageSlab(page));
 	return (struct slab *)page->lru.prev;
 }
 
 static inline struct kmem_cache *virt_to_cache(const void *obj)
 {
-	struct page *page = virt_to_page(obj);
+	struct page *page = virt_to_head_page(obj);
 	return page_get_cache(page);
 }
 
 static inline struct slab *virt_to_slab(const void *obj)
 {
-	struct page *page = virt_to_page(obj);
+	struct page *page = virt_to_head_page(obj);
 	return page_get_slab(page);
 }
 
@@ -2884,7 +2883,7 @@
 
 	objp -= obj_offset(cachep);
 	kfree_debugcheck(objp);
-	page = virt_to_page(objp);
+	page = virt_to_head_page(objp);
 
 	slabp = page_get_slab(page);
 
@@ -3108,7 +3107,7 @@
 		struct slab *slabp;
 		unsigned objnr;
 
-		slabp = page_get_slab(virt_to_page(objp));
+		slabp = page_get_slab(virt_to_head_page(objp));
 		objnr = (unsigned)(objp - slabp->s_mem) / cachep->buffer_size;
 		slab_bufctl(slabp)[objnr] = BUFCTL_ACTIVE;
 	}
mm/slub.c +4 -6
Index: linux-2.6.21-rc5-mm4/mm/slub.c
===================================================================
@@ -1297,9 +1297,7 @@
 {
 	struct page * page;
 
-	page = virt_to_page(x);
-
-	page = compound_head(page);
+	page = virt_to_head_page(x);
 
 	if (unlikely(PageError(page) && (s->flags & SLAB_STORE_USER)))
 		set_tracking(s, x, 1);
@@ -1310,7 +1308,7 @@
 /* Figure out on which slab object the object resides */
 static struct page *get_object_page(const void *x)
 {
-	struct page *page = compound_head(virt_to_page(x));
+	struct page *page = virt_to_head_page(x);
 
 	if (!PageSlab(page))
 		return NULL;
@@ -1952,7 +1950,7 @@
 	if (!x)
 		return;
 
-	page = compound_head(virt_to_page(x));
+	page = virt_to_head_page(x);
 
 	s = page->slab;
 
@@ -1988,7 +1986,7 @@
 		return NULL;
 	}
 
-	page = compound_head(virt_to_page(p));
+	page = virt_to_head_page(p);
 
 	new_cache = get_slab(new_size, flags);