diff mbox series

[v2] mm/page_alloc: optimize find_suitable_fallback() and fallbacks array

Message ID 20230209101144.496144-1-yajun.deng@linux.dev
State New
Headers
Series [v2] mm/page_alloc: optimize find_suitable_fallback() and fallbacks array |

Commit Message

Yajun Deng Feb. 9, 2023, 10:11 a.m. UTC 
  There is no need to execute the next loop if it not return in the first
loop. So add a break at the end of the loop.

At the same time, add !migratetype_is_mergeable() before the loop and
reduce the first index size from MIGRATE_TYPES to MIGRATE_PCPTYPES in
fallbacks array.

Signed-off-by: Yajun Deng <yajun.deng@linux.dev>
Acked-by: Vlastimil Babka <vbabka@suse.cz>
---
 include/linux/mmzone.h |  2 +-
 mm/page_alloc.c        | 11 +++++------
 2 files changed, 6 insertions(+), 7 deletions(-)

Comments

Zi Yan Feb. 9, 2023, 3:50 p.m. UTC | #1 
On 9 Feb 2023, at 5:11, Yajun Deng wrote:

> There is no need to execute the next loop if it not return in the first
> loop. So add a break at the end of the loop.

Can you explain why? If it is the case, MIGRATE_UNMOVABLE cannot fall back
to MIGRATE_MOVABLE? And MIGRATE_MOVABLE cannot fall back to MIGRATE_UNMOVABLE?
And MIGRATE_RECLAIMABLE cannot fall back to MIGRATE_MOVABLE?

>
> At the same time, add !migratetype_is_mergeable() before the loop and
> reduce the first index size from MIGRATE_TYPES to MIGRATE_PCPTYPES in
> fallbacks array.

You sent a patch: https://lore.kernel.org/all/20230203100132.1627787-1-yajun.deng@linux.dev/T/#u, why not squash this one into that? Why do
we need two separate small patches working on the same code?

Thanks.
>
> Signed-off-by: Yajun Deng <yajun.deng@linux.dev>
> Acked-by: Vlastimil Babka <vbabka@suse.cz>
> ---
>  include/linux/mmzone.h |  2 +-
>  mm/page_alloc.c        | 11 +++++------
>  2 files changed, 6 insertions(+), 7 deletions(-)
>
> diff --git a/include/linux/mmzone.h b/include/linux/mmzone.h
> index ab94985ee7d9..0a817b8c7fb2 100644
> --- a/include/linux/mmzone.h
> +++ b/include/linux/mmzone.h
> @@ -85,7 +85,7 @@ static inline bool is_migrate_movable(int mt)
>   * Check whether a migratetype can be merged with another migratetype.
>   *
>   * It is only mergeable when it can fall back to other migratetypes for
> - * allocation. See fallbacks[MIGRATE_TYPES][3] in page_alloc.c.
> + * allocation. See fallbacks[][] array in page_alloc.c.
>   */
>  static inline bool migratetype_is_mergeable(int mt)
>  {
> diff --git a/mm/page_alloc.c b/mm/page_alloc.c
> index 1113483fa6c5..536e8d838fb5 100644
> --- a/mm/page_alloc.c
> +++ b/mm/page_alloc.c
> @@ -2603,7 +2603,7 @@ struct page *__rmqueue_smallest(struct zone *zone, unsigned int order,
>   *
>   * The other migratetypes do not have fallbacks.
>   */
> -static int fallbacks[MIGRATE_TYPES][MIGRATE_PCPTYPES - 1] = {
> +static int fallbacks[MIGRATE_PCPTYPES][MIGRATE_PCPTYPES - 1] = {
>  	[MIGRATE_UNMOVABLE]   = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE   },
>  	[MIGRATE_MOVABLE]     = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE },
>  	[MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE,   MIGRATE_MOVABLE   },
> @@ -2861,7 +2861,7 @@ int find_suitable_fallback(struct free_area *area, unsigned int order,
>  	int i;
>  	int fallback_mt;
>
> -	if (area->nr_free == 0)
> +	if (area->nr_free == 0 || !migratetype_is_mergeable(migratetype))
>  		return -1;
>
>  	*can_steal = false;
> @@ -2873,11 +2873,10 @@ int find_suitable_fallback(struct free_area *area, unsigned int order,
>  		if (can_steal_fallback(order, migratetype))
>  			*can_steal = true;
>
> -		if (!only_stealable)
> -			return fallback_mt;
> -
> -		if (*can_steal)
> +		if (!only_stealable || *can_steal)
>  			return fallback_mt;
> +		else
> +			break;
>  	}
>
>  	return -1;
> -- 
> 2.25.1

--
Best Regards,
Yan, Zi
Yajun Deng Feb. 10, 2023, 1:57 a.m. UTC | #2 
February 9, 2023 11:50 PM, "Zi Yan" <ziy@nvidia.com> wrote:

> On 9 Feb 2023, at 5:11, Yajun Deng wrote:
> 
>> There is no need to execute the next loop if it not return in the first
>> loop. So add a break at the end of the loop.
> 
> Can you explain why? If it is the case, MIGRATE_UNMOVABLE cannot fall back
> to MIGRATE_MOVABLE? And MIGRATE_MOVABLE cannot fall back to MIGRATE_UNMOVABLE?
> And MIGRATE_RECLAIMABLE cannot fall back to MIGRATE_MOVABLE?
> 

The return in the loop is only related to 'order', 'migratetype' and 'only_stealable'
variables. Even if it execute the next loop, it can't change the result. So the loop
can be broken if the first loop can't return.

>> At the same time, add !migratetype_is_mergeable() before the loop and
>> reduce the first index size from MIGRATE_TYPES to MIGRATE_PCPTYPES in
>> fallbacks array.
> 
> You sent a patch: https://lore.kernel.org/all/20230203100132.1627787-1-yajun.deng@linux.dev/T/#u,
> why not squash this one into that? Why do
> we need two separate small patches working on the same code?
> 

Yes, this is better, but I overlooked this one when I sent the first patch. It is already merged.

As Vlastimil Babka said, reduce the first index from MIGRATE_TYPES to MIGRATE_PCPTYPES may be 
cause out of bounds access of the shrinked fallbacks array If we don't judge the range of 
migratetype. But this doesn't happen with the second index.

> Thanks.
> 
>> Signed-off-by: Yajun Deng <yajun.deng@linux.dev>
>> Acked-by: Vlastimil Babka <vbabka@suse.cz>
>> ---
>> include/linux/mmzone.h | 2 +-
>> mm/page_alloc.c | 11 +++++------
>> 2 files changed, 6 insertions(+), 7 deletions(-)
>> 
>> diff --git a/include/linux/mmzone.h b/include/linux/mmzone.h
>> index ab94985ee7d9..0a817b8c7fb2 100644
>> --- a/include/linux/mmzone.h
>> +++ b/include/linux/mmzone.h
>> @@ -85,7 +85,7 @@ static inline bool is_migrate_movable(int mt)
>> * Check whether a migratetype can be merged with another migratetype.
>> *
>> * It is only mergeable when it can fall back to other migratetypes for
>> - * allocation. See fallbacks[MIGRATE_TYPES][3] in page_alloc.c.
>> + * allocation. See fallbacks[][] array in page_alloc.c.
>> */
>> static inline bool migratetype_is_mergeable(int mt)
>> {
>> diff --git a/mm/page_alloc.c b/mm/page_alloc.c
>> index 1113483fa6c5..536e8d838fb5 100644
>> --- a/mm/page_alloc.c
>> +++ b/mm/page_alloc.c
>> @@ -2603,7 +2603,7 @@ struct page *__rmqueue_smallest(struct zone *zone, unsigned int order,
>> *
>> * The other migratetypes do not have fallbacks.
>> */
>> -static int fallbacks[MIGRATE_TYPES][MIGRATE_PCPTYPES - 1] = {
>> +static int fallbacks[MIGRATE_PCPTYPES][MIGRATE_PCPTYPES - 1] = {
>> [MIGRATE_UNMOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE },
>> [MIGRATE_MOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE },
>> [MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE, MIGRATE_MOVABLE },
>> @@ -2861,7 +2861,7 @@ int find_suitable_fallback(struct free_area *area, unsigned int order,
>> int i;
>> int fallback_mt;
>> 
>> - if (area->nr_free == 0)
>> + if (area->nr_free == 0 || !migratetype_is_mergeable(migratetype))
>> return -1;
>> 
>> *can_steal = false;
>> @@ -2873,11 +2873,10 @@ int find_suitable_fallback(struct free_area *area, unsigned int order,
>> if (can_steal_fallback(order, migratetype))
>> *can_steal = true;
>> 
>> - if (!only_stealable)
>> - return fallback_mt;
>> -
>> - if (*can_steal)
>> + if (!only_stealable || *can_steal)
>> return fallback_mt;
>> + else
>> + break;
>> }
>> 
>> return -1;
>> --
>> 2.25.1
> 
> --
> Best Regards,
> Yan, Zi
Zi Yan Feb. 10, 2023, 2:14 a.m. UTC | #3 
On 9 Feb 2023, at 20:57, Yajun Deng wrote:

> February 9, 2023 11:50 PM, "Zi Yan" <ziy@nvidia.com> wrote:
>
>> On 9 Feb 2023, at 5:11, Yajun Deng wrote:
>>
>>> There is no need to execute the next loop if it not return in the first
>>> loop. So add a break at the end of the loop.
>>
>> Can you explain why? If it is the case, MIGRATE_UNMOVABLE cannot fall back
>> to MIGRATE_MOVABLE? And MIGRATE_MOVABLE cannot fall back to MIGRATE_UNMOVABLE?
>> And MIGRATE_RECLAIMABLE cannot fall back to MIGRATE_MOVABLE?
>>
>
> The return in the loop is only related to 'order', 'migratetype' and 'only_stealable'
> variables. Even if it execute the next loop, it can't change the result. So the loop
> can be broken if the first loop can't return.

OK. Got it. Would the code below look better?

        for (i = 0; i < MIGRATE_PCPTYPES - 1 ; i++) {
                fallback_mt = fallbacks[migratetype][i];
                if (free_area_empty(area, fallback_mt))
                        continue;
        }

        if (can_steal_fallback(order, migratetype))
                *can_steal = true;

        if (!only_stealable || *can_steal)
                return fallback_mt;

        return -1;

>
>>> At the same time, add !migratetype_is_mergeable() before the loop and
>>> reduce the first index size from MIGRATE_TYPES to MIGRATE_PCPTYPES in
>>> fallbacks array.
>>
>> You sent a patch: https://lore.kernel.org/all/20230203100132.1627787-1-yajun.deng@linux.dev/T/#u,
>> why not squash this one into that? Why do
>> we need two separate small patches working on the same code?
>>
>
> Yes, this is better, but I overlooked this one when I sent the first patch. It is already merged.
>
> As Vlastimil Babka said, reduce the first index from MIGRATE_TYPES to MIGRATE_PCPTYPES may be
> cause out of bounds access of the shrinked fallbacks array If we don't judge the range of
> migratetype. But this doesn't happen with the second index.
>
>> Thanks.
>>
>>> Signed-off-by: Yajun Deng <yajun.deng@linux.dev>
>>> Acked-by: Vlastimil Babka <vbabka@suse.cz>
>>> ---
>>> include/linux/mmzone.h | 2 +-
>>> mm/page_alloc.c | 11 +++++------
>>> 2 files changed, 6 insertions(+), 7 deletions(-)
>>>
>>> diff --git a/include/linux/mmzone.h b/include/linux/mmzone.h
>>> index ab94985ee7d9..0a817b8c7fb2 100644
>>> --- a/include/linux/mmzone.h
>>> +++ b/include/linux/mmzone.h
>>> @@ -85,7 +85,7 @@ static inline bool is_migrate_movable(int mt)
>>> * Check whether a migratetype can be merged with another migratetype.
>>> *
>>> * It is only mergeable when it can fall back to other migratetypes for
>>> - * allocation. See fallbacks[MIGRATE_TYPES][3] in page_alloc.c.
>>> + * allocation. See fallbacks[][] array in page_alloc.c.
>>> */
>>> static inline bool migratetype_is_mergeable(int mt)
>>> {
>>> diff --git a/mm/page_alloc.c b/mm/page_alloc.c
>>> index 1113483fa6c5..536e8d838fb5 100644
>>> --- a/mm/page_alloc.c
>>> +++ b/mm/page_alloc.c
>>> @@ -2603,7 +2603,7 @@ struct page *__rmqueue_smallest(struct zone *zone, unsigned int order,
>>> *
>>> * The other migratetypes do not have fallbacks.
>>> */
>>> -static int fallbacks[MIGRATE_TYPES][MIGRATE_PCPTYPES - 1] = {
>>> +static int fallbacks[MIGRATE_PCPTYPES][MIGRATE_PCPTYPES - 1] = {
>>> [MIGRATE_UNMOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE },
>>> [MIGRATE_MOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE },
>>> [MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE, MIGRATE_MOVABLE },
>>> @@ -2861,7 +2861,7 @@ int find_suitable_fallback(struct free_area *area, unsigned int order,
>>> int i;
>>> int fallback_mt;
>>>
>>> - if (area->nr_free == 0)
>>> + if (area->nr_free == 0 || !migratetype_is_mergeable(migratetype))
>>> return -1;
>>>
>>> *can_steal = false;
>>> @@ -2873,11 +2873,10 @@ int find_suitable_fallback(struct free_area *area, unsigned int order,
>>> if (can_steal_fallback(order, migratetype))
>>> *can_steal = true;
>>>
>>> - if (!only_stealable)
>>> - return fallback_mt;
>>> -
>>> - if (*can_steal)
>>> + if (!only_stealable || *can_steal)
>>> return fallback_mt;
>>> + else
>>> + break;
>>> }
>>>
>>> return -1;
>>> --
>>> 2.25.1
>>
>> --
>> Best Regards,
>> Yan, Zi


--
Best Regards,
Yan, Zi
Yajun Deng Feb. 10, 2023, 2:33 a.m. UTC | #4 
February 10, 2023 10:14 AM, "Zi Yan" <ziy@nvidia.com> wrote:

> On 9 Feb 2023, at 20:57, Yajun Deng wrote:
> 
>> February 9, 2023 11:50 PM, "Zi Yan" <ziy@nvidia.com> wrote:
>> 
>>> On 9 Feb 2023, at 5:11, Yajun Deng wrote:
>> 
>> There is no need to execute the next loop if it not return in the first
>> loop. So add a break at the end of the loop.
>>> Can you explain why? If it is the case, MIGRATE_UNMOVABLE cannot fall back
>>> to MIGRATE_MOVABLE? And MIGRATE_MOVABLE cannot fall back to MIGRATE_UNMOVABLE?
>>> And MIGRATE_RECLAIMABLE cannot fall back to MIGRATE_MOVABLE?
>> 
>> The return in the loop is only related to 'order', 'migratetype' and 'only_stealable'
>> variables. Even if it execute the next loop, it can't change the result. So the loop
>> can be broken if the first loop can't return.
> 
> OK. Got it. Would the code below look better?
> 
> for (i = 0; i < MIGRATE_PCPTYPES - 1 ; i++) {
> fallback_mt = fallbacks[migratetype][i];
> if (free_area_empty(area, fallback_mt))
> continue;
> }
> 
> if (can_steal_fallback(order, migratetype))
> *can_steal = true;
> 
> if (!only_stealable || *can_steal)
> return fallback_mt;
> 
> return -1;
> 

Yes, I'll submit a v3 patch. 
Thanks.

>> At the same time, add !migratetype_is_mergeable() before the loop and
>> reduce the first index size from MIGRATE_TYPES to MIGRATE_PCPTYPES in
>> fallbacks array.
>>> You sent a patch: https://lore.kernel.org/all/20230203100132.1627787-1-yajun.deng@linux.dev/T/#u,
>>> why not squash this one into that? Why do
>>> we need two separate small patches working on the same code?
>> 
>> Yes, this is better, but I overlooked this one when I sent the first patch. It is already merged.
>> 
>> As Vlastimil Babka said, reduce the first index from MIGRATE_TYPES to MIGRATE_PCPTYPES may be
>> cause out of bounds access of the shrinked fallbacks array If we don't judge the range of
>> migratetype. But this doesn't happen with the second index.
>> 
>>> Thanks.
>> 
>> Signed-off-by: Yajun Deng <yajun.deng@linux.dev>
>> Acked-by: Vlastimil Babka <vbabka@suse.cz>
>> ---
>> include/linux/mmzone.h | 2 +-
>> mm/page_alloc.c | 11 +++++------
>> 2 files changed, 6 insertions(+), 7 deletions(-)
>> 
>> diff --git a/include/linux/mmzone.h b/include/linux/mmzone.h
>> index ab94985ee7d9..0a817b8c7fb2 100644
>> --- a/include/linux/mmzone.h
>> +++ b/include/linux/mmzone.h
>> @@ -85,7 +85,7 @@ static inline bool is_migrate_movable(int mt)
>> * Check whether a migratetype can be merged with another migratetype.
>> *
>> * It is only mergeable when it can fall back to other migratetypes for
>> - * allocation. See fallbacks[MIGRATE_TYPES][3] in page_alloc.c.
>> + * allocation. See fallbacks[][] array in page_alloc.c.
>> */
>> static inline bool migratetype_is_mergeable(int mt)
>> {
>> diff --git a/mm/page_alloc.c b/mm/page_alloc.c
>> index 1113483fa6c5..536e8d838fb5 100644
>> --- a/mm/page_alloc.c
>> +++ b/mm/page_alloc.c
>> @@ -2603,7 +2603,7 @@ struct page *__rmqueue_smallest(struct zone *zone, unsigned int order,
>> *
>> * The other migratetypes do not have fallbacks.
>> */
>> -static int fallbacks[MIGRATE_TYPES][MIGRATE_PCPTYPES - 1] = {
>> +static int fallbacks[MIGRATE_PCPTYPES][MIGRATE_PCPTYPES - 1] = {
>> [MIGRATE_UNMOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE },
>> [MIGRATE_MOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE },
>> [MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE, MIGRATE_MOVABLE },
>> @@ -2861,7 +2861,7 @@ int find_suitable_fallback(struct free_area *area, unsigned int order,
>> int i;
>> int fallback_mt;
>> 
>> - if (area->nr_free == 0)
>> + if (area->nr_free == 0 || !migratetype_is_mergeable(migratetype))
>> return -1;
>> 
>> *can_steal = false;
>> @@ -2873,11 +2873,10 @@ int find_suitable_fallback(struct free_area *area, unsigned int order,
>> if (can_steal_fallback(order, migratetype))
>> *can_steal = true;
>> 
>> - if (!only_stealable)
>> - return fallback_mt;
>> -
>> - if (*can_steal)
>> + if (!only_stealable || *can_steal)
>> return fallback_mt;
>> + else
>> + break;
>> }
>> 
>> return -1;
>> --
>> 2.25.1
>>> --
>>> Best Regards,
>>> Yan, Zi
> 
> --
> Best Regards,
> Yan, Zi
Yajun Deng Feb. 10, 2023, 2:51 a.m. UTC | #5 
February 10, 2023 10:33 AM, "Yajun Deng" <yajun.deng@linux.dev> wrote:

> February 10, 2023 10:14 AM, "Zi Yan" <ziy@nvidia.com> wrote:
> 
>> On 9 Feb 2023, at 20:57, Yajun Deng wrote:
>> 
>>> February 9, 2023 11:50 PM, "Zi Yan" <ziy@nvidia.com> wrote:
>> 
>> On 9 Feb 2023, at 5:11, Yajun Deng wrote:
>>> There is no need to execute the next loop if it not return in the first
>>> loop. So add a break at the end of the loop.
>> 
>> Can you explain why? If it is the case, MIGRATE_UNMOVABLE cannot fall back
>> to MIGRATE_MOVABLE? And MIGRATE_MOVABLE cannot fall back to MIGRATE_UNMOVABLE?
>> And MIGRATE_RECLAIMABLE cannot fall back to MIGRATE_MOVABLE?
>>> The return in the loop is only related to 'order', 'migratetype' and 'only_stealable'
>>> variables. Even if it execute the next loop, it can't change the result. So the loop
>>> can be broken if the first loop can't return.
>> 
>> OK. Got it. Would the code below look better?
>> 
>> for (i = 0; i < MIGRATE_PCPTYPES - 1 ; i++) {
>> fallback_mt = fallbacks[migratetype][i];
>> if (free_area_empty(area, fallback_mt))
>> continue;
>> }
>> 
>> if (can_steal_fallback(order, migratetype))
>> *can_steal = true;
>> 
>> if (!only_stealable || *can_steal)
>> return fallback_mt;
>> 
>> return -1;
> 
> Yes, I'll submit a v3 patch.
> Thanks.
> 

I found a logical error in your code. It should be like this:

        for (i = 0; i < MIGRATE_PCPTYPES - 1 ; i++) {
                fallback_mt = fallbacks[migratetype][i];
                if (!free_area_empty(area, fallback_mt))
                        break;
        }

        if (can_steal_fallback(order, migratetype))
                *can_steal = true;

        if (!only_stealable || *can_steal)
                return fallback_mt;

        return -1;

This code will modify the logic to the opposite.
So can anyone tell me if I should use this code or the v2 patch?


>>> At the same time, add !migratetype_is_mergeable() before the loop and
>>> reduce the first index size from MIGRATE_TYPES to MIGRATE_PCPTYPES in
>>> fallbacks array.
>> 
>> You sent a patch: https://lore.kernel.org/all/20230203100132.1627787-1-yajun.deng@linux.dev/T/#u,
>> why not squash this one into that? Why do
>> we need two separate small patches working on the same code?
>>> Yes, this is better, but I overlooked this one when I sent the first patch. It is already merged.
>>> 
>>> As Vlastimil Babka said, reduce the first index from MIGRATE_TYPES to MIGRATE_PCPTYPES may be
>>> cause out of bounds access of the shrinked fallbacks array If we don't judge the range of
>>> migratetype. But this doesn't happen with the second index.
>> 
>> Thanks.
>>> Signed-off-by: Yajun Deng <yajun.deng@linux.dev>
>>> Acked-by: Vlastimil Babka <vbabka@suse.cz>
>>> ---
>>> include/linux/mmzone.h | 2 +-
>>> mm/page_alloc.c | 11 +++++------
>>> 2 files changed, 6 insertions(+), 7 deletions(-)
>>> 
>>> diff --git a/include/linux/mmzone.h b/include/linux/mmzone.h
>>> index ab94985ee7d9..0a817b8c7fb2 100644
>>> --- a/include/linux/mmzone.h
>>> +++ b/include/linux/mmzone.h
>>> @@ -85,7 +85,7 @@ static inline bool is_migrate_movable(int mt)
>>> * Check whether a migratetype can be merged with another migratetype.
>>> *
>>> * It is only mergeable when it can fall back to other migratetypes for
>>> - * allocation. See fallbacks[MIGRATE_TYPES][3] in page_alloc.c.
>>> + * allocation. See fallbacks[][] array in page_alloc.c.
>>> */
>>> static inline bool migratetype_is_mergeable(int mt)
>>> {
>>> diff --git a/mm/page_alloc.c b/mm/page_alloc.c
>>> index 1113483fa6c5..536e8d838fb5 100644
>>> --- a/mm/page_alloc.c
>>> +++ b/mm/page_alloc.c
>>> @@ -2603,7 +2603,7 @@ struct page *__rmqueue_smallest(struct zone *zone, unsigned int order,
>>> *
>>> * The other migratetypes do not have fallbacks.
>>> */
>>> -static int fallbacks[MIGRATE_TYPES][MIGRATE_PCPTYPES - 1] = {
>>> +static int fallbacks[MIGRATE_PCPTYPES][MIGRATE_PCPTYPES - 1] = {
>>> [MIGRATE_UNMOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE },
>>> [MIGRATE_MOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE },
>>> [MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE, MIGRATE_MOVABLE },
>>> @@ -2861,7 +2861,7 @@ int find_suitable_fallback(struct free_area *area, unsigned int order,
>>> int i;
>>> int fallback_mt;
>>> 
>>> - if (area->nr_free == 0)
>>> + if (area->nr_free == 0 || !migratetype_is_mergeable(migratetype))
>>> return -1;
>>> 
>>> *can_steal = false;
>>> @@ -2873,11 +2873,10 @@ int find_suitable_fallback(struct free_area *area, unsigned int order,
>>> if (can_steal_fallback(order, migratetype))
>>> *can_steal = true;
>>> 
>>> - if (!only_stealable)
>>> - return fallback_mt;
>>> -
>>> - if (*can_steal)
>>> + if (!only_stealable || *can_steal)
>>> return fallback_mt;
>>> + else
>>> + break;
>>> }
>>> 
>>> return -1;
>>> --
>>> 2.25.1
>> 
>> --
>> Best Regards,
>> Yan, Zi
>> 
>> --
>> Best Regards,
>> Yan, Zi
Vlastimil Babka Feb. 10, 2023, 7:58 a.m. UTC | #6 
On 2/10/23 03:51, Yajun Deng wrote:
> February 10, 2023 10:33 AM, "Yajun Deng" <yajun.deng@linux.dev> wrote:
> 
>> February 10, 2023 10:14 AM, "Zi Yan" <ziy@nvidia.com> wrote:
>> 
>>> On 9 Feb 2023, at 20:57, Yajun Deng wrote:
>>> 
>>>> February 9, 2023 11:50 PM, "Zi Yan" <ziy@nvidia.com> wrote:
>>> 
>>> On 9 Feb 2023, at 5:11, Yajun Deng wrote:
>>>> There is no need to execute the next loop if it not return in the first
>>>> loop. So add a break at the end of the loop.
>>> 
>>> Can you explain why? If it is the case, MIGRATE_UNMOVABLE cannot fall back
>>> to MIGRATE_MOVABLE? And MIGRATE_MOVABLE cannot fall back to MIGRATE_UNMOVABLE?
>>> And MIGRATE_RECLAIMABLE cannot fall back to MIGRATE_MOVABLE?
>>>> The return in the loop is only related to 'order', 'migratetype' and 'only_stealable'
>>>> variables. Even if it execute the next loop, it can't change the result. So the loop
>>>> can be broken if the first loop can't return.
>>> 
>>> OK. Got it. Would the code below look better?
>>> 
>>> for (i = 0; i < MIGRATE_PCPTYPES - 1 ; i++) {
>>> fallback_mt = fallbacks[migratetype][i];
>>> if (free_area_empty(area, fallback_mt))
>>> continue;
>>> }
>>> 
>>> if (can_steal_fallback(order, migratetype))
>>> *can_steal = true;
>>> 
>>> if (!only_stealable || *can_steal)
>>> return fallback_mt;
>>> 
>>> return -1;
>> 
>> Yes, I'll submit a v3 patch.
>> Thanks.
>> 
> 
> I found a logical error in your code. It should be like this:
> 
>         for (i = 0; i < MIGRATE_PCPTYPES - 1 ; i++) {
>                 fallback_mt = fallbacks[migratetype][i];
>                 if (!free_area_empty(area, fallback_mt))
>                         break;
>         }
> 
>         if (can_steal_fallback(order, migratetype))
>                 *can_steal = true;
> 
>         if (!only_stealable || *can_steal)
>                 return fallback_mt;
> 
>         return -1;
> 
> This code will modify the logic to the opposite.

It's still wrong, IMHO. If all fallbacks have free_area_empty(), it will
return the last one and not -1. Also will set *can_steal in such case.

> So can anyone tell me if I should use this code or the v2 patch?

Once that bugs are fixed, the result will probably not look much better than
v2, so I don't mind keeping v2.
Yajun Deng Feb. 10, 2023, 8:12 a.m. UTC | #7 
February 10, 2023 3:58 PM, "Vlastimil Babka" <vbabka@suse.cz> wrote:

> On 2/10/23 03:51, Yajun Deng wrote:
> 
>> February 10, 2023 10:33 AM, "Yajun Deng" <yajun.deng@linux.dev> wrote:
>> 
>>> February 10, 2023 10:14 AM, "Zi Yan" <ziy@nvidia.com> wrote:
>> 
>> On 9 Feb 2023, at 20:57, Yajun Deng wrote:
>> 
>> February 9, 2023 11:50 PM, "Zi Yan" <ziy@nvidia.com> wrote:
>> 
>> On 9 Feb 2023, at 5:11, Yajun Deng wrote:
>> There is no need to execute the next loop if it not return in the first
>> loop. So add a break at the end of the loop.
>> 
>> Can you explain why? If it is the case, MIGRATE_UNMOVABLE cannot fall back
>> to MIGRATE_MOVABLE? And MIGRATE_MOVABLE cannot fall back to MIGRATE_UNMOVABLE?
>> And MIGRATE_RECLAIMABLE cannot fall back to MIGRATE_MOVABLE?
>> The return in the loop is only related to 'order', 'migratetype' and 'only_stealable'
>> variables. Even if it execute the next loop, it can't change the result. So the loop
>> can be broken if the first loop can't return.
>> 
>> OK. Got it. Would the code below look better?
>> 
>> for (i = 0; i < MIGRATE_PCPTYPES - 1 ; i++) {
>> fallback_mt = fallbacks[migratetype][i];
>> if (free_area_empty(area, fallback_mt))
>> continue;
>> }
>> 
>> if (can_steal_fallback(order, migratetype))
>> *can_steal = true;
>> 
>> if (!only_stealable || *can_steal)
>> return fallback_mt;
>> 
>> return -1;
>>> Yes, I'll submit a v3 patch.
>>> Thanks.
>> 
>> I found a logical error in your code. It should be like this:
>> 
>> for (i = 0; i < MIGRATE_PCPTYPES - 1 ; i++) {
>> fallback_mt = fallbacks[migratetype][i];
>> if (!free_area_empty(area, fallback_mt))
>> break;
>> }
>> 
>> if (can_steal_fallback(order, migratetype))
>> *can_steal = true;
>> 
>> if (!only_stealable || *can_steal)
>> return fallback_mt;
>> 
>> return -1;
>> 
>> This code will modify the logic to the opposite.
> 
> It's still wrong, IMHO. If all fallbacks have free_area_empty(), it will
> return the last one and not -1. Also will set *can_steal in such case.
> 

Yes, you are right.

>> So can anyone tell me if I should use this code or the v2 patch?
> 
> Once that bugs are fixed, the result will probably not look much better than
> v2, so I don't mind keeping v2.

I agree with that.
diff mbox series

Patch

diff --git a/include/linux/mmzone.h b/include/linux/mmzone.h
index ab94985ee7d9..0a817b8c7fb2 100644
--- a/include/linux/mmzone.h
+++ b/include/linux/mmzone.h
@@ -85,7 +85,7 @@  static inline bool is_migrate_movable(int mt)
  * Check whether a migratetype can be merged with another migratetype.
  *
  * It is only mergeable when it can fall back to other migratetypes for
- * allocation. See fallbacks[MIGRATE_TYPES][3] in page_alloc.c.
+ * allocation. See fallbacks[][] array in page_alloc.c.
  */
 static inline bool migratetype_is_mergeable(int mt)
 {
diff --git a/mm/page_alloc.c b/mm/page_alloc.c
index 1113483fa6c5..536e8d838fb5 100644
--- a/mm/page_alloc.c
+++ b/mm/page_alloc.c
@@ -2603,7 +2603,7 @@  struct page *__rmqueue_smallest(struct zone *zone, unsigned int order,
  *
  * The other migratetypes do not have fallbacks.
  */
-static int fallbacks[MIGRATE_TYPES][MIGRATE_PCPTYPES - 1] = {
+static int fallbacks[MIGRATE_PCPTYPES][MIGRATE_PCPTYPES - 1] = {
 	[MIGRATE_UNMOVABLE]   = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE   },
 	[MIGRATE_MOVABLE]     = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE },
 	[MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE,   MIGRATE_MOVABLE   },
@@ -2861,7 +2861,7 @@  int find_suitable_fallback(struct free_area *area, unsigned int order,
 	int i;
 	int fallback_mt;
 
-	if (area->nr_free == 0)
+	if (area->nr_free == 0 || !migratetype_is_mergeable(migratetype))
 		return -1;
 
 	*can_steal = false;
@@ -2873,11 +2873,10 @@  int find_suitable_fallback(struct free_area *area, unsigned int order,
 		if (can_steal_fallback(order, migratetype))
 			*can_steal = true;
 
-		if (!only_stealable)
-			return fallback_mt;
-
-		if (*can_steal)
+		if (!only_stealable || *can_steal)
 			return fallback_mt;
+		else
+			break;
 	}
 
 	return -1;