Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1539218 > unrolled thread

[PATCH 1/2] mm, page_alloc: don't convert pfn to idx when merging

Back to article view | Back to linux.kernel

Contents

  [PATCH 1/2] mm, page_alloc: don't convert pfn to idx when merging Vlastimil Babka <vbabka@suse.cz> - 2016-12-09 10:40 +0100
    Re: [PATCH 1/2] mm, page_alloc: don't convert pfn to idx when merging kbuild test robot <lkp@intel.com> - 2016-12-09 13:20 +0100
      Re: [PATCH 1/2] mm, page_alloc: don't convert pfn to idx when merging Vlastimil Babka <vbabka@suse.cz> - 2016-12-09 13:40 +0100
    Re: [PATCH 1/2] mm, page_alloc: don't convert pfn to idx when merging Mel Gorman <mgorman@techsingularity.net> - 2016-12-09 18:30 +0100
      Re: [PATCH 1/2] mm, page_alloc: don't convert pfn to idx when merging Vlastimil Babka <vbabka@suse.cz> - 2016-12-09 19:40 +0100
        Re: [PATCH 1/2] mm, page_alloc: don't convert pfn to idx when merging Mel Gorman <mgorman@techsingularity.net> - 2016-12-09 20:50 +0100

#1539218 — [PATCH 1/2] mm, page_alloc: don't convert pfn to idx when merging

In __free_one_page() we do the buddy merging arithmetics on "page/buddy index",
which is just the lower MAX_ORDER bits of pfn. The operations we do that affect
the higher bits are bitwise AND and subtraction (in that order), where the
final result will be the same with the higher bits left unmasked, as long as
these bits are equal for both buddies - which must be true by the definition of
a buddy.

We can therefore use pfn's directly instead of "index" and skip the zeroing of
>MAX_ORDER bits. This can help a bit by itself, although compiler might be
smart enough already. It also helps the next patch to avoid page_to_pfn() for
memory hole checks.

Signed-off-by: Vlastimil Babka <vbabka@suse.cz>
---
 mm/internal.h   |  4 ++--
 mm/page_alloc.c | 33 +++++++++++++++------------------
 2 files changed, 17 insertions(+), 20 deletions(-)

diff --git a/mm/internal.h b/mm/internal.h
index 537ac9951f5f..6d20f0e52b74 100644
--- a/mm/internal.h
+++ b/mm/internal.h
@@ -131,9 +131,9 @@ struct alloc_context {
  * Assumption: *_mem_map is contiguous at least up to MAX_ORDER
  */
 static inline unsigned long
-__find_buddy_index(unsigned long page_idx, unsigned int order)
+__find_buddy_pfn(unsigned long page_pfn, unsigned int order)
 {
-	return page_idx ^ (1 << order);
+	return page_pfn ^ (1 << order);
 }
 
 extern struct page *__pageblock_pfn_to_page(unsigned long start_pfn,
diff --git a/mm/page_alloc.c b/mm/page_alloc.c
index 6de9440e3ae2..812475bff8f3 100644
--- a/mm/page_alloc.c
+++ b/mm/page_alloc.c
@@ -783,13 +783,12 @@ static inline int page_is_buddy(struct page *page, struct page *buddy,
  */
 
 static inline void __free_one_page(struct page *page,
-		unsigned long pfn,
+		unsigned long page_pfn,
 		struct zone *zone, unsigned int order,
 		int migratetype)
 {
-	unsigned long page_idx;
-	unsigned long combined_idx;
-	unsigned long uninitialized_var(buddy_idx);
+	unsigned long combined_pfn;
+	unsigned long uninitialized_var(buddy_pfn);
 	struct page *buddy;
 	unsigned int max_order;
 
@@ -802,15 +801,13 @@ static inline void __free_one_page(struct page *page,
 	if (likely(!is_migrate_isolate(migratetype)))
 		__mod_zone_freepage_state(zone, 1 << order, migratetype);
 
-	page_idx = pfn & ((1 << MAX_ORDER) - 1);
-
-	VM_BUG_ON_PAGE(page_idx & ((1 << order) - 1), page);
+	VM_BUG_ON_PAGE(page_pfn & ((1 << order) - 1), page);
 	VM_BUG_ON_PAGE(bad_range(zone, page), page);
 
 continue_merging:
 	while (order < max_order - 1) {
-		buddy_idx = __find_buddy_index(page_idx, order);
-		buddy = page + (buddy_idx - page_idx);
+		buddy_pfn = __find_buddy_pfn(page_pfn, order);
+		buddy = page + (buddy_pfn - page_pfn);
 		if (!page_is_buddy(page, buddy, order))
 			goto done_merging;
 		/*
@@ -824,9 +821,9 @@ static inline void __free_one_page(struct page *page,
 			zone->free_area[order].nr_free--;
 			rmv_page_order(buddy);
 		}
-		combined_idx = buddy_idx & page_idx;
-		page = page + (combined_idx - page_idx);
-		page_idx = combined_idx;
+		combined_pfn = buddy_pfn & page_pfn;
+		page = page + (combined_pfn - page_pfn);
+		page_pfn = combined_pfn;
 		order++;
 	}
 	if (max_order < MAX_ORDER) {
@@ -841,8 +838,8 @@ static inline void __free_one_page(struct page *page,
 		if (unlikely(has_isolate_pageblock(zone))) {
 			int buddy_mt;
 
-			buddy_idx = __find_buddy_index(page_idx, order);
-			buddy = page + (buddy_idx - page_idx);
+			buddy_pfn = __find_buddy_pfn(page_pfn, order);
+			buddy = page + (buddy_pfn - page_pfn);
 			buddy_mt = get_pageblock_migratetype(buddy);
 
 			if (migratetype != buddy_mt
@@ -867,10 +864,10 @@ static inline void __free_one_page(struct page *page,
 	 */
 	if ((order < MAX_ORDER-2) && pfn_valid_within(page_to_pfn(buddy))) {
 		struct page *higher_page, *higher_buddy;
-		combined_idx = buddy_idx & page_idx;
-		higher_page = page + (combined_idx - page_idx);
-		buddy_idx = __find_buddy_index(combined_idx, order + 1);
-		higher_buddy = higher_page + (buddy_idx - combined_idx);
+		combined_pfn = buddy_pfn & page_pfn;
+		higher_page = page + (combined_pfn - page_pfn);
+		buddy_pfn = __find_buddy_pfn(combined_pfn, order + 1);
+		higher_buddy = higher_page + (buddy_pfn - combined_pfn);
 		if (page_is_buddy(higher_page, higher_buddy, order + 1)) {
 			list_add_tail(&page->lru,
 				&zone->free_area[order].free_list[migratetype]);
-- 
2.11.0

[toc] | [next] | [standalone]

#1539314

[Multipart message — attachments visible in raw view] — view raw

Hi Vlastimil,

[auto build test ERROR on mmotm/master]
[also build test ERROR on v4.9-rc8 next-20161208]
[if your patch is applied to the wrong git tree, please drop us a note to help improve the system]

url:    https://github.com/0day-ci/linux/commits/Vlastimil-Babka/mm-page_alloc-don-t-convert-pfn-to-idx-when-merging/20161209-192634
base:   git://git.cmpxchg.org/linux-mmotm.git master
config: i386-randconfig-s1-201649 (attached as .config)
compiler: gcc-6 (Debian 6.2.0-3) 6.2.0 20160901
reproduce:
        # save the attached .config to linux build tree
        make ARCH=i386 

All errors (new ones prefixed by >>):

   mm/page_isolation.c: In function 'unset_migratetype_isolate':
>> mm/page_isolation.c:106:16: error: implicit declaration of function '__find_buddy_index' [-Werror=implicit-function-declaration]
       buddy_idx = __find_buddy_index(page_idx, order);
                   ^~~~~~~~~~~~~~~~~~
   Cyclomatic Complexity 5 include/linux/compiler.h:__read_once_size
   Cyclomatic Complexity 1 arch/x86/include/asm/bitops.h:variable_test_bit
   Cyclomatic Complexity 1 include/linux/list.h:hlist_empty
   Cyclomatic Complexity 1 include/linux/cpumask.h:cpumask_check
   Cyclomatic Complexity 1 include/linux/cpumask.h:cpumask_test_cpu
   Cyclomatic Complexity 1 arch/x86/include/asm/atomic.h:atomic_read
   Cyclomatic Complexity 2 arch/x86/include/asm/jump_label.h:arch_static_branch
   Cyclomatic Complexity 1 include/linux/jump_label.h:static_key_false
   Cyclomatic Complexity 5 arch/x86/include/asm/preempt.h:__preempt_count_add
   Cyclomatic Complexity 5 arch/x86/include/asm/preempt.h:__preempt_count_sub
   Cyclomatic Complexity 1 include/linux/spinlock.h:spinlock_check
   Cyclomatic Complexity 1 include/linux/spinlock.h:spin_unlock_irqrestore
   Cyclomatic Complexity 1 include/linux/nodemask.h:node_state
   Cyclomatic Complexity 1 include/linux/rcupdate.h:rcu_read_lock_sched_notrace
   Cyclomatic Complexity 1 include/linux/rcupdate.h:rcu_read_unlock_sched_notrace
   Cyclomatic Complexity 2 include/linux/notifier.h:notifier_to_errno
   Cyclomatic Complexity 1 arch/x86/include/asm/topology.h:numa_node_id
   Cyclomatic Complexity 1 include/linux/topology.h:numa_mem_id
   Cyclomatic Complexity 1 include/linux/gfp.h:gfp_zonelist
   Cyclomatic Complexity 1 include/linux/gfp.h:node_zonelist
   Cyclomatic Complexity 1 include/linux/gfp.h:__alloc_pages
   Cyclomatic Complexity 2 include/linux/gfp.h:__alloc_pages_node
   Cyclomatic Complexity 2 include/linux/gfp.h:alloc_pages_node
   Cyclomatic Complexity 1 include/linux/page-flags.h:PageHighMem
   Cyclomatic Complexity 1 include/linux/page-flags.h:PageHWPoison
   Cyclomatic Complexity 1 include/linux/page-flags.h:PageHuge
   Cyclomatic Complexity 1 include/linux/page-flags.h:PageBuddy
   Cyclomatic Complexity 1 include/linux/mm.h:page_zonenum
   Cyclomatic Complexity 1 include/linux/mm.h:page_zone
   Cyclomatic Complexity 2 include/linux/vmstat.h:__mod_zone_freepage_state
   Cyclomatic Complexity 1 include/linux/page-isolation.h:is_migrate_isolate_page
   Cyclomatic Complexity 1 include/linux/memory.h:memory_isolate_notify
   Cyclomatic Complexity 1 mm/internal.h:page_order
   Cyclomatic Complexity 6 include/trace/events/page_isolation.h:trace_test_pages_isolated
   Cyclomatic Complexity 1 include/linux/seq_buf.h:seq_buf_has_overflowed
   Cyclomatic Complexity 3 include/linux/trace_seq.h:trace_seq_has_overflowed
   Cyclomatic Complexity 1 arch/x86/include/asm/stacktrace.h:caller_frame_pointer
   Cyclomatic Complexity 1 include/linux/perf_event.h:perf_fetch_caller_regs
   Cyclomatic Complexity 1 include/linux/trace_events.h:trace_handle_return
   Cyclomatic Complexity 5 include/linux/trace_events.h:trace_trigger_soft_disabled
   Cyclomatic Complexity 1 include/trace/events/page_isolation.h:trace_event_get_offsets_test_pages_isolated
   Cyclomatic Complexity 2 mm/page_isolation.c:__first_valid_page
   Cyclomatic Complexity 5 mm/page_isolation.c:__test_page_isolated_in_pageblock
   Cyclomatic Complexity 4 include/trace/events/page_isolation.h:trace_event_define_fields_test_pages_isolated
   Cyclomatic Complexity 6 include/trace/events/page_isolation.h:perf_trace_test_pages_isolated
   Cyclomatic Complexity 3 include/trace/events/page_isolation.h:trace_event_raw_event_test_pages_isolated
   Cyclomatic Complexity 3 include/trace/events/page_isolation.h:trace_raw_output_test_pages_isolated
   Cyclomatic Complexity 5 mm/page_isolation.c:set_migratetype_isolate
   Cyclomatic Complexity 7 mm/page_isolation.c:unset_migratetype_isolate
   Cyclomatic Complexity 5 mm/page_isolation.c:start_isolate_page_range
   Cyclomatic Complexity 4 mm/page_isolation.c:undo_isolate_page_range
   Cyclomatic Complexity 6 mm/page_isolation.c:test_pages_isolated
   Cyclomatic Complexity 3 mm/page_isolation.c:alloc_migrate_target
   cc1: some warnings being treated as errors

vim +/__find_buddy_index +106 mm/page_isolation.c

3c605096 Joonsoo Kim 2014-11-13  100  	 * these pages to be merged.
3c605096 Joonsoo Kim 2014-11-13  101  	 */
3c605096 Joonsoo Kim 2014-11-13  102  	if (PageBuddy(page)) {
3c605096 Joonsoo Kim 2014-11-13  103  		order = page_order(page);
3c605096 Joonsoo Kim 2014-11-13  104  		if (order >= pageblock_order) {
3c605096 Joonsoo Kim 2014-11-13  105  			page_idx = page_to_pfn(page) & ((1 << MAX_ORDER) - 1);
3c605096 Joonsoo Kim 2014-11-13 @106  			buddy_idx = __find_buddy_index(page_idx, order);
3c605096 Joonsoo Kim 2014-11-13  107  			buddy = page + (buddy_idx - page_idx);
3c605096 Joonsoo Kim 2014-11-13  108  
1ae7013d Hui Zhu     2015-05-14  109  			if (pfn_valid_within(page_to_pfn(buddy)) &&

:::::: The code at line 106 was first introduced by commit
:::::: 3c605096d3158216ba9326a16266f6ba128c2c8d mm/page_alloc: restrict max order of merging on isolated pageblock

:::::: TO: Joonsoo Kim <iamjoonsoo.kim@lge.com>
:::::: CC: Linus Torvalds <torvalds@linux-foundation.org>

---
0-DAY kernel test infrastructure                Open Source Technology Center
https://lists.01.org/pipermail/kbuild-all                   Intel Corporation

[toc] | [prev] | [next] | [standalone]

#1539321

On 12/09/2016 01:14 PM, kbuild test robot wrote:
> Hi Vlastimil,
>
> [auto build test ERROR on mmotm/master]
> [also build test ERROR on v4.9-rc8 next-20161208]
> [if your patch is applied to the wrong git tree, please drop us a note to help improve the system]
>
> url:    https://github.com/0day-ci/linux/commits/Vlastimil-Babka/mm-page_alloc-don-t-convert-pfn-to-idx-when-merging/20161209-192634
> base:   git://git.cmpxchg.org/linux-mmotm.git master
> config: i386-randconfig-s1-201649 (attached as .config)
> compiler: gcc-6 (Debian 6.2.0-3) 6.2.0 20160901
> reproduce:
>         # save the attached .config to linux build tree
>         make ARCH=i386
>
> All errors (new ones prefixed by >>):
>
>    mm/page_isolation.c: In function 'unset_migratetype_isolate':
>>> mm/page_isolation.c:106:16: error: implicit declaration of function '__find_buddy_index' [-Werror=implicit-function-declaration]
>        buddy_idx = __find_buddy_index(page_idx, order);
>                    ^~~~~~~~~~~~~~~~~~

Looks like my .config was missing MEMORY_ISOLATION. Fix is trivial and 
will include in v2 eventually after feedback.

[toc] | [prev] | [next] | [standalone]

#1539567

On Fri, Dec 09, 2016 at 10:37:53AM +0100, Vlastimil Babka wrote:
> In __free_one_page() we do the buddy merging arithmetics on "page/buddy index",
> which is just the lower MAX_ORDER bits of pfn. The operations we do that affect
> the higher bits are bitwise AND and subtraction (in that order), where the
> final result will be the same with the higher bits left unmasked, as long as
> these bits are equal for both buddies - which must be true by the definition of
> a buddy.

Ok, other than the kbuild warning, both patchs look ok. I expect the
benefit is marginal but every little bit helps.

> 
> We can therefore use pfn's directly instead of "index" and skip the zeroing of
> >MAX_ORDER bits. This can help a bit by itself, although compiler might be
> smart enough already. It also helps the next patch to avoid page_to_pfn() for
> memory hole checks.
> 

I expect this benefit only applies to a few archiectures and won't be
visible on x86 but it still makes sense so for both patches;

Acked-by: Mel Gorman <mgorman@techsingularity.net>

As a slight aside, I recently spotted that one of the largest overhead
in the bulk free path was in the page_is_buddy() checks so pretty much
anything that helps that is welcome.

-- 
Mel Gorman
SUSE Labs

[toc] | [prev] | [next] | [standalone]

#1539614

On 12/09/2016 06:26 PM, Mel Gorman wrote:
> On Fri, Dec 09, 2016 at 10:37:53AM +0100, Vlastimil Babka wrote:
>> In __free_one_page() we do the buddy merging arithmetics on "page/buddy index",
>> which is just the lower MAX_ORDER bits of pfn. The operations we do that affect
>> the higher bits are bitwise AND and subtraction (in that order), where the
>> final result will be the same with the higher bits left unmasked, as long as
>> these bits are equal for both buddies - which must be true by the definition of
>> a buddy.
> 
> Ok, other than the kbuild warning, both patchs look ok. I expect the
> benefit is marginal but every little bit helps.
> 
>>
>> We can therefore use pfn's directly instead of "index" and skip the zeroing of
>>> MAX_ORDER bits. This can help a bit by itself, although compiler might be
>> smart enough already. It also helps the next patch to avoid page_to_pfn() for
>> memory hole checks.
>>
> 
> I expect this benefit only applies to a few archiectures and won't be
> visible on x86 but it still makes sense so for both patches;
> 
> Acked-by: Mel Gorman <mgorman@techsingularity.net>

Thanks!

> As a slight aside, I recently spotted that one of the largest overhead
> in the bulk free path was in the page_is_buddy() checks so pretty much
> anything that helps that is welcome.

Interesting, the function shouldn't be doing really much on x86 without
debug config options? We might try further optimize the zone equivalence
checks, perhaps?
- try caching page_zone_id(page) through whole merging, and only obtain
it freshly
  for buddy candidate
- mark arches/configurations sane enough that they have no zone boundary
within MAX_ORDER, and skip these checks there. I assume most, if not all
x86 would fall here? Somewhat analogically to page_valid_within().

[toc] | [prev] | [next] | [standalone]

#1539634

On Fri, Dec 09, 2016 at 07:32:22PM +0100, Vlastimil Babka wrote:
> > As a slight aside, I recently spotted that one of the largest overhead
> > in the bulk free path was in the page_is_buddy() checks so pretty much
> > anything that helps that is welcome.
> 
> Interesting, the function shouldn't be doing really much on x86 without
> debug config options? We might try further optimize the zone equivalence
> checks, perhaps?

I don't have the data any more but IIRC, it was cache miss intensive and
I assumed at the time that it was checking cache cold struct pages
during merges.

At the time I was looking at splitting the per-cpu lists into irq and
non-irq so wasn't focused on the page_is_buddy part of the profile. It
just stuck in my mind as being surprisingly high.

-- 
Mel Gorman
SUSE Labs

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web