Skip to contentSkip to conversation

Bloat caused by unnecessary calls to compound_head()?

PATCH New Eric Biggers 3 participants 8 messages Mar 26, 2016 – Apr 4, 2016

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

Hi,

I noticed that after the recent "page-flags" patchset, there are an excessive number of calls to compound_head() in certain places.

For example, the frequently executed mark_page_accessed() function already starts out by calling compound_head(), but then each time it tests a page flag afterwards, there is an extra, seemingly unnecessary, call to compound_head(). This causes a series of instructions like the following to appear no fewer than 10 times throughout the function:

ffffffff81119db4:       48 8b 53 20             mov    0x20(%rbx),%rdx
ffffffff81119db8:       48 8d 42 ff             lea    -0x1(%rdx),%rax
ffffffff81119dbc:       83 e2 01                and    $0x1,%edx
ffffffff81119dbf:       48 0f 44 c3             cmove  %rbx,%rax
ffffffff81119dc3:       48 8b 00                mov    (%rax),%rax

Part of the problem, I suppose, is that the compiler doesn't know that the pages can't be linked more than one level deep.

Is this a known tradeoff, and have any possible solutions been considered?

Eric

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

#1 lore raw
Quoted 17 lines · Eric Biggers

Hi,

I noticed that after the recent "page-flags" patchset, there are an excessive number of calls to compound_head() in certain places.

For example, the frequently executed mark_page_accessed() function already starts out by calling compound_head(), but then each time it tests a page flag afterwards, there is an extra, seemingly unnecessary, call to compound_head(). This causes a series of instructions like the following to appear no fewer than 10 times throughout the function:

ffffffff81119db4:       48 8b 53 20             mov    0x20(%rbx),%rdx
ffffffff81119db8:       48 8d 42 ff             lea    -0x1(%rdx),%rax
ffffffff81119dbc:       83 e2 01                and    $0x1,%edx
ffffffff81119dbf:       48 0f 44 c3             cmove  %rbx,%rax
ffffffff81119dc3:       48 8b 00                mov    (%rax),%rax
Quoted 4 lines

Part of the problem, I suppose, is that the compiler doesn't know that the pages can't be linked more than one level deep.

Is this a known tradeoff, and have any possible solutions been considered?

<I'm sick, so my judgment may be off>

Yes, it's known problem. And I've tried to approach it few times without satisfying results.

Your mail made me try again.

The idea is to introduce new type to indicate head page -- 'struct head_page' -- it's compatible with struct page on memory layout, but distinct from C point of view. compound_head() should return pointer of that type. For the proof-of-concept I've introduced new helper -- compound_head_t().

Then we can make page-flag helpers to accept both types, by converting them to macros and use __builtin_types_compatible_p().

When a page-flag helper sees pointer to 'struct head_page' as an argument, it can safely assume that it deals with head or non-compound page and therefore can bypass all policy restrictions and get rid of compound_head() calls.

I'll send proof-of-concept patches in reply to this message. The code is not pretty. I myself consider the idea rather ugly.

Any comments are welcome.

Signature · 7 lines
 Kirill A. Shutemov

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
#4 lore raw

PATCH 3/4 page-flags: make page flag helpers accept struct head_page

In reply to Kirill A. Shutemov

This patch makes all generated page flag helpers to accept pointer to struct head_page as well as struct page.

In case if pointer to struct head_page is passed, we assume that it's head page and bypass policy constrain checks.

Note, to get get inteface consistent we would need to make non-generated page flag helper to accept struct head_page as well.

---
 scripts/mkpageflags.sh | 16 ++++++++++------
 1 file changed, 10 insertions(+), 6 deletions(-)
scripts/mkpageflags.sh +10 -6
index 29d46bccaea4..272aab4ad1a3 100755
@@ -6,23 +6,23 @@ fatal() {
 }
 
 any() {
-	echo "(__p)"
+	echo "((struct page *)(__p))"
 }
 
 head() {
-	echo "compound_head(__p)"
+	echo "compound_head((struct page *)(__p))"
 }
 
 no_tail() {
 	local enforce="${1:+VM_BUG_ON_PGFLAGS(PageTail(__p), __p);}"
 
-	echo "({$enforce compound_head(__p);})"
+	echo "({$enforce compound_head((struct page *)(__p));})"
 }
 
 no_compound() {
 	local enforce="${1:+VM_BUG_ON_PGFLAGS(PageCompound(__p), __p);}"
 
-	echo "({$enforce __p;})"
+	echo "({$enforce ((struct page *)(__p));})"
 }
 
 generate_test() {
@@ -34,7 +34,9 @@ generate_test() {
 	cat <<EOF
 #define $uname(__p) ({								\\
 	int ret;								\\
-	if (__builtin_types_compatible_p(typeof(*(__p)), struct page))		\\
+	if (__builtin_types_compatible_p(typeof(*(__p)), struct head_page))	\\
+		ret = $op(PG_$lname, &((struct head_page *)(__p))->page.flags);	\\
+	else if (__builtin_types_compatible_p(typeof(*(__p)), struct page))	\\
 		ret = $op(PG_$lname, &$page->flags);				\\
 	else									\\
 		BUILD_BUG();							\\
@@ -52,7 +54,9 @@ generate_mod() {
 
 	cat <<EOF
 #define $uname(__p) do {							\\
-	if (__builtin_types_compatible_p(typeof(*(__p)), struct page))		\\
+	if (__builtin_types_compatible_p(typeof(*(__p)), struct head_page))	\\
+		$op(PG_$lname, &((struct head_page *)(__p))->page.flags);	\\
+	else if (__builtin_types_compatible_p(typeof(*(__p)), struct page))	\\
 		$op(PG_$lname, &$page->flags);					\\
 	else									\\
 		BUILD_BUG();							\\
Signature · 7 lines
2.8.0.rc3

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
#3 lore raw

PATCH 2/4 mm: introduce struct head_page and compound_head_t

In reply to Kirill A. Shutemov

This patch creates new type that is compatible with struct page on memory layout, but distinct from C point of view.

compound_head_t() has the same functionality as compound_head(), but returns pointer on struct head_page.

---
 include/linux/mm_types.h   | 4 ++++
 include/linux/page-flags.h | 9 ++++++++-
 2 files changed, 12 insertions(+), 1 deletion(-)
include/linux/mm_types.h +4 -0
index 944b2b37313b..247e86adaa1c 100644
@@ -225,6 +225,10 @@ struct page {
 #endif
 ;
 
+struct head_page {
+	struct page page;
+};
+
 struct page_frag {
 	struct page *page;
 #if (BITS_PER_LONG > 32) || (PAGE_SIZE >= 65536)
include/linux/page-flags.h +8 -1
index d111caad2a22..54801253b85c 100644
@@ -133,7 +133,9 @@ enum pageflags {
 
 #ifndef __GENERATING_BOUNDS_H
 
-struct page;	/* forward declaration */
+/* forward declaration */
+struct page;
+struct head_page;
 
 static inline struct page *compound_head(struct page *page)
 {
@@ -144,6 +146,11 @@ static inline struct page *compound_head(struct page *page)
 	return page;
 }
 
+static inline struct head_page *compound_head_t(struct page *page)
+{
+	return (struct head_page *)compound_head(page);
+}
+
 static __always_inline int PageTail(struct page *page)
 {
 	return READ_ONCE(page->compound_head) & 1;
Signature · 7 lines
2.8.0.rc3

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
#5 lore raw

PATCH 4/4 mm: convert make_page_accessed to use compount_page_t()

In reply to Kirill A. Shutemov

Just for example, convert one function to just created interface.

This way we cut size of the function by third:

function                                     old     new   delta
mark_page_accessed                           310     203    -107
---
 mm/swap.c | 15 ++++++++-------
 1 file changed, 8 insertions(+), 7 deletions(-)
mm/swap.c +8 -7
index 09fe5e97714a..1fe072ae6ee1 100644
@@ -360,9 +360,10 @@ static void __lru_cache_activate_page(struct page *page)
  */
 void mark_page_accessed(struct page *page)
 {
-	page = compound_head(page);
-	if (!PageActive(page) && !PageUnevictable(page) &&
-			PageReferenced(page)) {
+	struct head_page *head = compound_head_t(page);
+	page = &head->page;
+	if (!PageActive(head) && !PageUnevictable(head) &&
+			PageReferenced(head)) {
 
 		/*
 		 * If the page is on the LRU, queue it for activation via
@@ -370,15 +371,15 @@ void mark_page_accessed(struct page *page)
 		 * pagevec, mark it active and it'll be moved to the active
 		 * LRU on the next drain.
 		 */
-		if (PageLRU(page))
+		if (PageLRU(head))
 			activate_page(page);
 		else
 			__lru_cache_activate_page(page);
-		ClearPageReferenced(page);
+		ClearPageReferenced(head);
 		if (page_is_file_cache(page))
 			workingset_activation(page);
-	} else if (!PageReferenced(page)) {
-		SetPageReferenced(page);
+	} else if (!PageReferenced(head)) {
+		SetPageReferenced(head);
 	}
 	if (page_is_idle(page))
 		clear_page_idle(page);
Signature · 7 lines
2.8.0.rc3

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
#2 lore raw

PATCH 1/4 page-flags: generate page-flags helpers with script

In reply to Kirill A. Shutemov

scripts/mkpageflags.sh generates include/generated/page-flags.h using directive in mm/page-flags.tlb.

Format of the mm/page-flags.tlb: lines not started with capital letter, just copied. Lines which starts with capital letter are rules to generate page-flags helper:

<uname> <lname> <policy> <required-helpers>

Result of generation is set of helper macros, not functions. It's required for future extension.

Type safety is controlled with __builtin_types_compatible_p() check.

---
 Kbuild                     |  30 +++++--
 include/linux/page-flags.h | 217 +--------------------------------------------
 mm/page-flags.tbl          | 102 +++++++++++++++++++++
 scripts/mkpageflags.sh     | 151 +++++++++++++++++++++++++++++++
 4 files changed, 279 insertions(+), 221 deletions(-)
 create mode 100644 mm/page-flags.tbl
 create mode 100755 scripts/mkpageflags.sh
Kbuild +25 -5
index f55cefd9bf29..405c7145af95 100644
@@ -3,8 +3,9 @@
 # This file takes care of the following:
 # 1) Generate bounds.h
 # 2) Generate timeconst.h
-# 3) Generate asm-offsets.h (may need bounds.h and timeconst.h)
-# 4) Check for missing system calls
+# 3) Generate page-flags.h
+# 4) Generate asm-offsets.h (may need bounds.h, timeconst.h and page-flags.h)
+# 5) Check for missing system calls
 
 # Default sed regexp - multiline due to syntax constraints
 define sed-y
@@ -66,7 +67,25 @@ $(obj)/$(timeconst-file): kernel/time/timeconst.bc FORCE
 	$(call filechk,gentimeconst)
 
 #####
-# 3) Generate asm-offsets.h
+# 3) Generate page-flags.h
+
+pageflags-file := include/generated/page-flags.h
+
+targets += $(pageflags-file)
+
+quiet_cmd_genpageflags = GEN     $@
+define cmd_genpageflags
+	$(srctree)/scripts/mkpageflags.sh <$< >$@
+endef
+define filechk_genpageflags
+	$(srctree)/scripts/mkpageflags.sh <$<
+endef
+
+$(obj)/$(pageflags-file): mm/page-flags.tbl FORCE
+	$(call filechk,genpageflags)
+
+#####
+# 4) Generate asm-offsets.h
 #
 
 offsets-file := include/generated/asm-offsets.h
@@ -76,7 +95,8 @@ targets += arch/$(SRCARCH)/kernel/asm-offsets.s
 
 # We use internal kbuild rules to avoid the "is up to date" message from make
 arch/$(SRCARCH)/kernel/asm-offsets.s: arch/$(SRCARCH)/kernel/asm-offsets.c \
-                                      $(obj)/$(timeconst-file) $(obj)/$(bounds-file) FORCE
+                                      $(obj)/$(timeconst-file) $(obj)/$(bounds-file) \
+                                      $(obj)/$(pageflags-file) FORCE
 	$(Q)mkdir -p $(dir $@)
 	$(call if_changed_dep,cc_s_c)
 
@@ -84,7 +104,7 @@ $(obj)/$(offsets-file): arch/$(SRCARCH)/kernel/asm-offsets.s FORCE
 	$(call filechk,offsets,__ASM_OFFSETS_H__)
 
 #####
-# 4) Check for missing system calls
+# 5) Check for missing system calls
 #
 
 always += missing-syscalls
include/linux/page-flags.h +1 -216

259 lines not on this page · raw message

mm/page-flags.tbl new file +102 -0

102 lines not on this page · raw message

scripts/mkpageflags.sh new file +151 -0

151 lines not on this page · raw message

Signature · 7 lines
2.8.0.rc3

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
#6 lore raw
In reply to Kirill A. Shutemov
Quoted 6 lines · Kirill A. Shutemov

The idea is to introduce new type to indicate head page -- 'struct head_page' -- it's compatible with struct page on memory layout, but distinct from C point of view. compound_head() should return pointer of that type. For the proof-of-concept I've introduced new helper -- compound_head_t().

Well, it's good for optimizing the specific case of mark_page_accessed(). I'm more worried about the general level of bloat, since the Page* macros are used in so many places. And generating page-flags.h with a script is something to be avoided if at all possible.

I wasn't following the discussion around the original page-flags patchset. Can you point me to a discussion of the benefits of the page "policy" checks --- why are they suddenly needed when they weren't before? Or any helpful comments in the code?

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

#7 lore raw
Quoted 8 lines · Eric Biggers
Quoted 6 lines · Kirill A. Shutemov

The idea is to introduce new type to indicate head page -- 'struct head_page' -- it's compatible with struct page on memory layout, but distinct from C point of view. compound_head() should return pointer of that type. For the proof-of-concept I've introduced new helper -- compound_head_t().

Quoted 4 lines

Well, it's good for optimizing the specific case of mark_page_accessed(). I'm more worried about the general level of bloat, since the Page* macros are used in so many places. And generating page-flags.h with a script is something to be avoided if at all possible.

I think it can be done without generating page-flags.h. We can generate with preprocessor Head* helpers in addition to Page*. New heplers would opperate with struct head_page rather than struct page.

Quoted 4 lines

I wasn't following the discussion around the original page-flags patchset. Can you point me to a discussion of the benefits of the page "policy" checks --- why are they suddenly needed when they weren't before? Or any helpful comments in the code?

Recent THP refcounting rework (went into v4.5) made possible mapping part of huge page with PTEs. Basically, we now have page table entries which point to tail pages. It means we have tail pages in codepaths where we haven't before and we need to deal with this.

Many of the flags apply to whole compound page, not a subpage. So we need to redirect page flag operation to head page.

Signature · 7 lines
 Kirill A. Shutemov

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>