Fixup the page of buddy_higher address's calculation

Fixup the page of buddy_higher address's calculation

[Li Haifeng]

>From d7cd78f9d71a5c9ddeed02724558096f0bb4508a Mon Sep 17 00:00:00 2001
From: Haifeng Li <omycle@gmail.com>
Date: Thu, 23 Aug 2012 16:27:19 +0800
Subject: [PATCH] Fixup the page of buddy_higher address's calculation

Signed-off-by: Haifeng Li <omycle@gmail.com>
---
 mm/page_alloc.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/mm/page_alloc.c b/mm/page_alloc.c
index ddbc17d..5588f68 100644
--- a/mm/page_alloc.c
+++ b/mm/page_alloc.c
@@ -579,7 +579,7 @@ static inline void __free_one_page(struct page *page,
                combined_idx = buddy_idx & page_idx;
                higher_page = page + (combined_idx - page_idx);
                buddy_idx = __find_buddy_index(combined_idx, order + 1);
-               higher_buddy = page + (buddy_idx - combined_idx);
+               higher_buddy = page + (buddy_idx - page_idx);
                if (page_is_buddy(higher_page, higher_buddy, order + 1)) {
                        list_add_tail(&page->lru,
                                &zone->free_area[order].free_list[migratetype]);
--
1.7.5.4

Re: Fixup the page of buddy_higher address's calculation

[Michal Hocko]

On Thu 23-08-12 16:40:13, Li Haifeng wrote:
> From d7cd78f9d71a5c9ddeed02724558096f0bb4508a Mon Sep 17 00:00:00 2001
> From: Haifeng Li <omycle@gmail.com>
> Date: Thu, 23 Aug 2012 16:27:19 +0800
> Subject: [PATCH] Fixup the page of buddy_higher address's calculation

Some general questions:
Any word about the change? Is it really that obvious? Why do you think the
current state is incorrect? How did you find out?

And more specific below:

> Signed-off-by: Haifeng Li <omycle@gmail.com>
> ---
>  mm/page_alloc.c |    2 +-
>  1 files changed, 1 insertions(+), 1 deletions(-)
> 
> diff --git a/mm/page_alloc.c b/mm/page_alloc.c
> index ddbc17d..5588f68 100644
> --- a/mm/page_alloc.c
> +++ b/mm/page_alloc.c
> @@ -579,7 +579,7 @@ static inline void __free_one_page(struct page *page,
>                 combined_idx = buddy_idx & page_idx;
>                 higher_page = page + (combined_idx - page_idx);
>                 buddy_idx = __find_buddy_index(combined_idx, order + 1);
> -               higher_buddy = page + (buddy_idx - combined_idx);
> +               higher_buddy = page + (buddy_idx - page_idx);

We are finding buddy index for combined_idx so why should we use
page_idx here?

>                 if (page_is_buddy(higher_page, higher_buddy, order + 1)) {
>                         list_add_tail(&page->lru,
>                                 &zone->free_area[order].free_list[migratetype]);
> --
> 1.7.5.4

-- 
Michal Hocko
SUSE Labs

Re: Fixup the page of buddy_higher address's calculation

[Li Haifeng]

I am sorry for my mistake.

higher_buddy is corresponding with buddy_index, and higher page is
corresponding with combined_idx. That is right.

But, How we get the page address from index offset? The key answer is
what is the base value.
So calculating the address based page should be (page + (buddy_idx - page_idx)).

Maybe, a diagram is easier to understand.

 |-------------------------|-------------|
page               combined   buddy

buddy's page address= page‘s page address + (buddy - page)*sizeof(struct page)

Clear?

2012/8/23 Michal Hocko <mhocko@suse.cz>:
> On Thu 23-08-12 16:40:13, Li Haifeng wrote:
>> From d7cd78f9d71a5c9ddeed02724558096f0bb4508a Mon Sep 17 00:00:00 2001
>> From: Haifeng Li <omycle@gmail.com>
>> Date: Thu, 23 Aug 2012 16:27:19 +0800
>> Subject: [PATCH] Fixup the page of buddy_higher address's calculation
>
> Some general questions:
> Any word about the change? Is it really that obvious? Why do you think the
> current state is incorrect? How did you find out?
>
> And more specific below:
>
>> Signed-off-by: Haifeng Li <omycle@gmail.com>
>> ---
>>  mm/page_alloc.c |    2 +-
>>  1 files changed, 1 insertions(+), 1 deletions(-)
>>
>> diff --git a/mm/page_alloc.c b/mm/page_alloc.c
>> index ddbc17d..5588f68 100644
>> --- a/mm/page_alloc.c
>> +++ b/mm/page_alloc.c
>> @@ -579,7 +579,7 @@ static inline void __free_one_page(struct page *page,
>>                 combined_idx = buddy_idx & page_idx;
>>                 higher_page = page + (combined_idx - page_idx);
>>                 buddy_idx = __find_buddy_index(combined_idx, order + 1);
>> -               higher_buddy = page + (buddy_idx - combined_idx);
>> +               higher_buddy = page + (buddy_idx - page_idx);
>
> We are finding buddy index for combined_idx so why should we use
> page_idx here?
>
>>                 if (page_is_buddy(higher_page, higher_buddy, order + 1)) {
>>                         list_add_tail(&page->lru,
>>                                 &zone->free_area[order].free_list[migratetype]);
>> --
>> 1.7.5.4
>
> --
> Michal Hocko
> SUSE Labs

Re: Fixup the page of buddy_higher address's calculation

[Michal Hocko]

On Thu 23-08-12 20:30:34, Gavin Shan wrote:
> On Thu, Aug 23, 2012 at 06:21:06PM +0800, Li Haifeng wrote:
[...]
> >>> From d7cd78f9d71a5c9ddeed02724558096f0bb4508a Mon Sep 17 00:00:00 2001
> >>> From: Haifeng Li <omycle@gmail.com>
> >>> Date: Thu, 23 Aug 2012 16:27:19 +0800
> >>> Subject: [PATCH] Fixup the page of buddy_higher address's calculation
> >>
> >> Some general questions:
> >> Any word about the change? Is it really that obvious? Why do you think the
> >> current state is incorrect? How did you find out?
> >>
> >> And more specific below:
> >>
> >>> Signed-off-by: Haifeng Li <omycle@gmail.com>
> >>> ---
> >>>  mm/page_alloc.c |    2 +-
> >>>  1 files changed, 1 insertions(+), 1 deletions(-)
> >>>
> >>> diff --git a/mm/page_alloc.c b/mm/page_alloc.c
> >>> index ddbc17d..5588f68 100644
> >>> --- a/mm/page_alloc.c
> >>> +++ b/mm/page_alloc.c
> >>> @@ -579,7 +579,7 @@ static inline void __free_one_page(struct page *page,
> >>>                 combined_idx = buddy_idx & page_idx;
> >>>                 higher_page = page + (combined_idx - page_idx);
> >>>                 buddy_idx = __find_buddy_index(combined_idx, order + 1);
> >>> -               higher_buddy = page + (buddy_idx - combined_idx);
> >>> +               higher_buddy = page + (buddy_idx - page_idx);
> 
> Haifeng, Not sure it would be better? At least, the expression
> would be more explicitly meaningful than yours.
> 
> 		    higher_buddy = higher_page + (buddy_idx - combined_idx);

Yes, indeed. It would be also good to mention that this is a regression
since 43506fad (mm/page_alloc.c: simplify calculation of combined index
of adjacent buddy lists). IIUC this basically disables the heuristic
because page_is_buddy will fail for order+1, right?

Maybe 2.6.38+ stable candidate, then.

Could you repost with the full changelog, please?

Thanks
-- 
Michal Hocko
SUSE Labs

Re: Fixup the page of buddy_higher address's calculation

[Li Haifeng]

2012/8/23 Michal Hocko <mhocko@suse.cz>:
> On Thu 23-08-12 20:30:34, Gavin Shan wrote:
>> On Thu, Aug 23, 2012 at 06:21:06PM +0800, Li Haifeng wrote:
> [...]
>> >>> From d7cd78f9d71a5c9ddeed02724558096f0bb4508a Mon Sep 17 00:00:00 2001
>> >>> From: Haifeng Li <omycle@gmail.com>
>> >>> Date: Thu, 23 Aug 2012 16:27:19 +0800
>> >>> Subject: [PATCH] Fixup the page of buddy_higher address's calculation
>> >>
>> >> Some general questions:
>> >> Any word about the change? Is it really that obvious? Why do you think the
>> >> current state is incorrect? How did you find out?
>> >>
>> >> And more specific below:
>> >>
>> >>> Signed-off-by: Haifeng Li <omycle@gmail.com>
>> >>> ---
>> >>>  mm/page_alloc.c |    2 +-
>> >>>  1 files changed, 1 insertions(+), 1 deletions(-)
>> >>>
>> >>> diff --git a/mm/page_alloc.c b/mm/page_alloc.c
>> >>> index ddbc17d..5588f68 100644
>> >>> --- a/mm/page_alloc.c
>> >>> +++ b/mm/page_alloc.c
>> >>> @@ -579,7 +579,7 @@ static inline void __free_one_page(struct page *page,
>> >>>                 combined_idx = buddy_idx & page_idx;
>> >>>                 higher_page = page + (combined_idx - page_idx);
>> >>>                 buddy_idx = __find_buddy_index(combined_idx, order + 1);
>> >>> -               higher_buddy = page + (buddy_idx - combined_idx);
>> >>> +               higher_buddy = page + (buddy_idx - page_idx);
>>
>> Haifeng, Not sure it would be better? At least, the expression
>> would be more explicitly meaningful than yours.
>>
>>                   higher_buddy = higher_page + (buddy_idx - combined_idx);
>
Thanks Gavin. Yes, it's more meaningful. :)

> Yes, indeed. It would be also good to mention that this is a regression
> since 43506fad (mm/page_alloc.c: simplify calculation of combined index
> of adjacent buddy lists). IIUC this basically disables the heuristic
> because page_is_buddy will fail for order+1, right?
>
> Maybe 2.6.38+ stable candidate, then.
>
> Could you repost with the full changelog, please?
>

OK.

> Thanks
> --
> Michal Hocko
> SUSE Labs

Also sorry for the confusing title. Repost it.
------------------------------------------------------>
Subject: [PATCH] Fix the page address of higher page's buddy calculation

Calculate the page address of higher page's buddy should be based
higher_page with the offset between index of higher page and
index of higher page's buddy.

Signed-off-by: Haifeng Li <omycle@gmail.com>
Signed-off-by: Gavin Shan <shangw@linux.vnet.ibm.com>
---
 mm/page_alloc.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/mm/page_alloc.c b/mm/page_alloc.c
index cdef1d4..642cd62 100644
--- a/mm/page_alloc.c
+++ b/mm/page_alloc.c
@@ -536,7 +536,7 @@ static inline void __free_one_page(struct page *page,
                combined_idx = buddy_idx & page_idx;
                higher_page = page + (combined_idx - page_idx);
                buddy_idx = __find_buddy_index(combined_idx, order + 1);
-               higher_buddy = page + (buddy_idx - combined_idx);
+               higher_buddy = higher_page + (buddy_idx - combined_idx);
                if (page_is_buddy(higher_page, higher_buddy, order + 1)) {
                        list_add_tail(&page->lru,
                                &zone->free_area[order].free_list[migratetype]);
--
1.7.5.4

Re: Fixup the page of buddy_higher address's calculation

[Michal Hocko]

On Fri 24-08-12 10:08:20, Li Haifeng wrote:
[...]
> Subject: [PATCH] Fix the page address of higher page's buddy calculation
> 
> Calculate the page address of higher page's buddy should be based
> higher_page with the offset between index of higher page and
> index of higher page's buddy.

Sorry for insisting but could you add an information about when this has
been introduced (I have mentioned the commit in the other email) and the
effect of the bug so that we can consider whether this is worth
backporting to stable trees.

> Signed-off-by: Haifeng Li <omycle@gmail.com>
> Signed-off-by: Gavin Shan <shangw@linux.vnet.ibm.com>

Other than that
Reviewed-by: Michal Hocko <mhocko@suse.cz>

> ---
>  mm/page_alloc.c |    2 +-
>  1 files changed, 1 insertions(+), 1 deletions(-)
> 
> diff --git a/mm/page_alloc.c b/mm/page_alloc.c
> index cdef1d4..642cd62 100644
> --- a/mm/page_alloc.c
> +++ b/mm/page_alloc.c
> @@ -536,7 +536,7 @@ static inline void __free_one_page(struct page *page,
>                 combined_idx = buddy_idx & page_idx;
>                 higher_page = page + (combined_idx - page_idx);
>                 buddy_idx = __find_buddy_index(combined_idx, order + 1);
> -               higher_buddy = page + (buddy_idx - combined_idx);
> +               higher_buddy = higher_page + (buddy_idx - combined_idx);
>                 if (page_is_buddy(higher_page, higher_buddy, order + 1)) {
>                         list_add_tail(&page->lru,
>                                 &zone->free_area[order].free_list[migratetype]);
> --
> 1.7.5.4

-- 
Michal Hocko
SUSE Labs

Re: Fixup the page of buddy_higher address's calculation

[Li Haifeng]

2012/8/24 Michal Hocko <mhocko@suse.cz>:
> On Fri 24-08-12 10:08:20, Li Haifeng wrote:
> [...]
>> Subject: [PATCH] Fix the page address of higher page's buddy calculation
>>
>> Calculate the page address of higher page's buddy should be based
>> higher_page with the offset between index of higher page and
>> index of higher page's buddy.
>
> Sorry for insisting but could you add an information about when this has
> been introduced (I have mentioned the commit in the other email) and the
> effect of the bug so that we can consider whether this is worth
> backporting to stable trees.
>
>> Signed-off-by: Haifeng Li <omycle@gmail.com>
>> Signed-off-by: Gavin Shan <shangw@linux.vnet.ibm.com>
>
> Other than that
> Reviewed-by: Michal Hocko <mhocko@suse.cz>
>
>> ---
>>  mm/page_alloc.c |    2 +-
>>  1 files changed, 1 insertions(+), 1 deletions(-)
>>
>> diff --git a/mm/page_alloc.c b/mm/page_alloc.c
>> index cdef1d4..642cd62 100644
>> --- a/mm/page_alloc.c
>> +++ b/mm/page_alloc.c
>> @@ -536,7 +536,7 @@ static inline void __free_one_page(struct page *page,
>>                 combined_idx = buddy_idx & page_idx;
>>                 higher_page = page + (combined_idx - page_idx);
>>                 buddy_idx = __find_buddy_index(combined_idx, order + 1);
>> -               higher_buddy = page + (buddy_idx - combined_idx);
>> +               higher_buddy = higher_page + (buddy_idx - combined_idx);
>>                 if (page_is_buddy(higher_page, higher_buddy, order + 1)) {
>>                         list_add_tail(&page->lru,
>>                                 &zone->free_area[order].free_list[migratetype]);
>> --
>> 1.7.5.4
>
> --
> Michal Hocko
> SUSE Labs

I am sorry Michal. I misinterpreted what you mean.

And the post blow is OK?
------------------------------------------>
Subject: [PATCH] Fix the page address of higher page's buddy calculation

The heuristic method for buddy has been introduced since
43506fad(mm/page_alloc.c: simplify calculation of combined index
of adjacent buddy lists). But the page address of higher page's
buddy was wrongly calculated, which will lead page_is_buddy to
fail for ever. IOW, the heuristic method would be disabled with the wrong
page address of higher page's buddy.

Calculating the page address of higher page's buddy should be based
higher_page with the offset between index of higher page and
index of higher page's buddy.

Signed-off-by: Haifeng Li <omycle@gmail.com>
Signed-off-by: Gavin Shan <shangw@linux.vnet.ibm.com>
Reviewed-by: Michal Hocko <mhocko@suse.cz>
---
 mm/page_alloc.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/mm/page_alloc.c b/mm/page_alloc.c
index ddbc17d..0754a3c 100644
--- a/mm/page_alloc.c
+++ b/mm/page_alloc.c
@@ -579,7 +579,7 @@ static inline void __free_one_page(struct page *page,
                combined_idx = buddy_idx & page_idx;
                higher_page = page + (combined_idx - page_idx);
                buddy_idx = __find_buddy_index(combined_idx, order + 1);
-               higher_buddy = page + (buddy_idx - combined_idx);
+               higher_buddy = higher_page + (buddy_idx - combined_idx);
                if (page_is_buddy(higher_page, higher_buddy, order + 1)) {
                        list_add_tail(&page->lru,
                                &zone->free_area[order].free_list[migratetype]);
--
1.7.5.4

Re: Fixup the page of buddy_higher address's calculation

[Michal Hocko]

On Fri 24-08-12 17:08:36, Li Haifeng wrote:
> 2012/8/24 Michal Hocko <mhocko@suse.cz>:
> > On Fri 24-08-12 10:08:20, Li Haifeng wrote:
> > [...]
> >> Subject: [PATCH] Fix the page address of higher page's buddy calculation
> >>
> >> Calculate the page address of higher page's buddy should be based
> >> higher_page with the offset between index of higher page and
> >> index of higher page's buddy.
> >
> > Sorry for insisting but could you add an information about when this has
> > been introduced (I have mentioned the commit in the other email) and the
> > effect of the bug so that we can consider whether this is worth
> > backporting to stable trees.
> >
> >> Signed-off-by: Haifeng Li <omycle@gmail.com>
> >> Signed-off-by: Gavin Shan <shangw@linux.vnet.ibm.com>
> >
> > Other than that
> > Reviewed-by: Michal Hocko <mhocko@suse.cz>
> >
> >> ---
> >>  mm/page_alloc.c |    2 +-
> >>  1 files changed, 1 insertions(+), 1 deletions(-)
> >>
> >> diff --git a/mm/page_alloc.c b/mm/page_alloc.c
> >> index cdef1d4..642cd62 100644
> >> --- a/mm/page_alloc.c
> >> +++ b/mm/page_alloc.c
> >> @@ -536,7 +536,7 @@ static inline void __free_one_page(struct page *page,
> >>                 combined_idx = buddy_idx & page_idx;
> >>                 higher_page = page + (combined_idx - page_idx);
> >>                 buddy_idx = __find_buddy_index(combined_idx, order + 1);
> >> -               higher_buddy = page + (buddy_idx - combined_idx);
> >> +               higher_buddy = higher_page + (buddy_idx - combined_idx);
> >>                 if (page_is_buddy(higher_page, higher_buddy, order + 1)) {
> >>                         list_add_tail(&page->lru,
> >>                                 &zone->free_area[order].free_list[migratetype]);
> >> --
> >> 1.7.5.4
> >
> > --
> > Michal Hocko
> > SUSE Labs
> 
> I am sorry Michal. I misinterpreted what you mean.
> 
> And the post blow is OK?
> ------------------------------------------>
> Subject: [PATCH] Fix the page address of higher page's buddy calculation
> 
> The heuristic method for buddy has been introduced since
> 43506fad(mm/page_alloc.c: simplify calculation of combined index
> of adjacent buddy lists). 

Maybe I just misunderstood you here but the heuristic has been
introduced by 6dda9d55 (page allocator: reduce fragmentation in buddy
allocator by adding buddies that are merging to the tail of the free
lists) and the commit you are mentioning broke it.

> But the page address of higher page's buddy was wrongly calculated,
> which will lead page_is_buddy to fail for ever. IOW, the heuristic
> method would be disabled with the wrong page address of higher page's
> buddy.
> 
> Calculating the page address of higher page's buddy should be based
> higher_page with the offset between index of higher page and
> index of higher page's buddy.
>

I would also add CC: stable [2.6.38+] although it is not clear how much
the heuristic is helpful. Anyway it's a regression and should be fix
IMHO.

> Signed-off-by: Haifeng Li <omycle@gmail.com>
> Signed-off-by: Gavin Shan <shangw@linux.vnet.ibm.com>
> Reviewed-by: Michal Hocko <mhocko@suse.cz>
> ---
>  mm/page_alloc.c |    2 +-
>  1 files changed, 1 insertions(+), 1 deletions(-)
> 
> diff --git a/mm/page_alloc.c b/mm/page_alloc.c
> index ddbc17d..0754a3c 100644
> --- a/mm/page_alloc.c
> +++ b/mm/page_alloc.c
> @@ -579,7 +579,7 @@ static inline void __free_one_page(struct page *page,
>                 combined_idx = buddy_idx & page_idx;
>                 higher_page = page + (combined_idx - page_idx);
>                 buddy_idx = __find_buddy_index(combined_idx, order + 1);
> -               higher_buddy = page + (buddy_idx - combined_idx);
> +               higher_buddy = higher_page + (buddy_idx - combined_idx);
>                 if (page_is_buddy(higher_page, higher_buddy, order + 1)) {
>                         list_add_tail(&page->lru,
>                                 &zone->free_area[order].free_list[migratetype]);
> --
> 1.7.5.4

-- 
Michal Hocko
SUSE Labs