Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:3 as permitted sender) client-ip=2620:137:e000::3:3;
Feedback-ID: i84614614:Fastmail
References: <20230912175228.952039-1-shr@devkernel.io>
 <20230912175228.952039-2-shr@devkernel.io>
 <6447ab02-1a22-efe4-68c9-4f595e2499fc@redhat.com>
 <qvqwled3jvq2.fsf@devbig1114.prn1.facebook.com>
 <5bf3e7ad-b666-ae88-449a-074f17a9cbba@redhat.com>
User-agent: mu4e 1.10.1; emacs 28.2.50
From:   Stefan Roesch <shr@devkernel.io>
To:     David Hildenbrand <david@redhat.com>
Cc:     kernel-team@fb.com, akpm@linux-foundation.org, hannes@cmpxchg.org,
        riel@surriel.com, linux-kernel@vger.kernel.org, linux-mm@kvack.org
Subject: Re: [PATCH v1 1/4] mm/ksm: add "smart" page scanning mode
Date:   Mon, 18 Sep 2023 10:22:09 -0700
In-reply-to: <5bf3e7ad-b666-ae88-449a-074f17a9cbba@redhat.com>
Message-ID: <qvqwo7hz4cr3.fsf@devbig1114.prn1.facebook.com>
MIME-Version: 1.0
Content-Type: text/plain
Precedence: bulk


David Hildenbrand <david@redhat.com> writes:

> On 18.09.23 18:18, Stefan Roesch wrote:
>> David Hildenbrand <david@redhat.com> writes:
>>
>>> On 12.09.23 19:52, Stefan Roesch wrote:
>>>> This change adds a "smart" page scanning mode for KSM. So far all the
>>>> candidate pages are continuously scanned to find candidates for
>>>> de-duplication. There are a considerably number of pages that cannot be
>>>> de-duplicated. This is costly in terms of CPU. By using smart scanning
>>>> considerable CPU savings can be achieved.
>>>> This change takes the history of scanning pages into account and skips
>>>> the page scanning of certain pages for a while if de-deduplication for
>>>> this page has not been successful in the past.
>>>> To do this it introduces two new fields in the ksm_rmap_item structure:
>>>> age and skip_age. age, is the KSM age and skip_page is the age for how
>>>> long page scanning of this page is skipped. The age field is incremented
>>>> each time the page is scanned and the page cannot be de-duplicated.
>>>> How often a page is skipped is dependent how often de-duplication has
>>>> been tried so far and the number of skips is currently limited to 8.
>>>> This value has shown to be effective with different workloads.
>>>> The feature is currently disable by default and can be enabled with the
>>>> new smart_scan knob.
>>>> The feature has shown to be very effective: upt to 25% of the page scans
>>>> can be eliminated; the pages_to_scan rate can be reduced by 40 - 50% and
>>>> a similar de-duplication rate can be maintained.
>>>> Signed-off-by: Stefan Roesch <shr@devkernel.io>
>>>> ---
>>>>    mm/ksm.c | 75 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
>>>>    1 file changed, 75 insertions(+)
>>>> diff --git a/mm/ksm.c b/mm/ksm.c
>>>> index 981af9c72e7a..bfd5087c7d5a 100644
>>>> --- a/mm/ksm.c
>>>> +++ b/mm/ksm.c
>>>> @@ -56,6 +56,8 @@
>>>>    #define DO_NUMA(x)	do { } while (0)
>>>>    #endif
>>>>    +typedef u8 rmap_age_t;
>>>> +
>>>>    /**
>>>>     * DOC: Overview
>>>>     *
>>>> @@ -193,6 +195,8 @@ struct ksm_stable_node {
>>>>     * @node: rb node of this rmap_item in the unstable tree
>>>>     * @head: pointer to stable_node heading this list in the stable tree
>>>>     * @hlist: link into hlist of rmap_items hanging off that stable_node
>>>> + * @age: number of scan iterations since creation
>>>> + * @skip_age: skip rmap item until age reaches skip_age
>>>>     */
>>>>    struct ksm_rmap_item {
>>>>    	struct ksm_rmap_item *rmap_list;
>>>> @@ -212,6 +216,8 @@ struct ksm_rmap_item {
>>>>    			struct hlist_node hlist;
>>>>    		};
>>>>    	};
>>>> +	rmap_age_t age;
>>>> +	rmap_age_t skip_age;
>>>>    };
>>>>      #define SEQNR_MASK	0x0ff	/* low bits of unstable tree seqnr */
>>>> @@ -281,6 +287,9 @@ static unsigned int zero_checksum __read_mostly;
>>>>    /* Whether to merge empty (zeroed) pages with actual zero pages */
>>>>    static bool ksm_use_zero_pages __read_mostly;
>>>>    +/* Skip pages that couldn't be de-duplicated previously  */
>>>> +static bool ksm_smart_scan;
>>>> +
>>>>    /* The number of zero pages which is placed by KSM */
>>>>    unsigned long ksm_zero_pages;
>>>>    @@ -2305,6 +2314,45 @@ static struct ksm_rmap_item
>>>> *get_next_rmap_item(struct ksm_mm_slot *mm_slot,
>>>>    	return rmap_item;
>>>>    }
>>>>    +static unsigned int inc_skip_age(rmap_age_t age)
>>>> +{
>>>> +	if (age <= 3)
>>>> +		return 1;
>>>> +	if (age <= 5)
>>>> +		return 2;
>>>> +	if (age <= 8)
>>>> +		return 4;
>>>> +
>>>> +	return 8;
>>>> +}
>>>> +
>>>> +static bool skip_rmap_item(struct page *page, struct ksm_rmap_item *rmap_item)
>>>> +{
>>>> +	rmap_age_t age;
>>>> +
>>>> +	if (!ksm_smart_scan)
>>>> +		return false;
>>>> +
>>>> +	if (PageKsm(page))
>>>> +		return false;
>>>
>>>
>>> I'm a bit confused about this check here. scan_get_next_rmap_item() would return
>>> a PageKsm() page and call cmp_and_merge_page().
>>>
>>> cmp_and_merge_page() says: "first see if page can be merged into the stable
>>> tree"
>>>
>>> ... but shouldn't a PageKsm page *already* be in the stable tree?
>>>
>>> Maybe that's what cmp_and_merge_page() does via:
>>>
>>> 	kpage = stable_tree_search(page);
>>> 	if (kpage == page && rmap_item->head == stable_node) {
>>> 		put_page(kpage);
>>> 		return;
>>> 	}
>>>
>>>
>>> Hoping you can enlighten me :)
>>>
>> The above description sounds correct. During each scan we go through all
>> the candidate pages and this includes rmap_items that maps to KSM pages.
>> The above check simply skips these pages.
>
> Can we add a comment why we don't skip them? Like
>
> /*
>  * Never skip pages that are already KSM; pages cmp_and_merge_page()
>  * will essentially ignore them, but we still have to process them
>  * properly.
>  */
>

I'll add the comment in the next version.

>>
>>>> +
>>>> +	age = rmap_item->age++;
>>>
>>> Can't we overflow here? Is that desired, or would you want to stop at the
>>> maximum you can store?
>>>
>> Yes, we can overflow here and it was a deliberate choice. If we overflow
>> after we tried unsuccessfully for 255 times, we re-start with shorter
>> skip values, but that should be fine. In return we avoid an if statement.
>> The age is defined as unsigned.
>
> Can we make that explicit instead? Dealing with implicit overflows really makes
> the code harder to grasp.
>

I'll make it explicit.

>>
>>>> +	if (age < 3)
>>>> +		return false;
>>>> +
>>>> +	if (rmap_item->skip_age == age) {
>>>> +		rmap_item->skip_age = 0;
>>>> +		return false;
>>>> +	}
>>>> +
>>>> +	if (rmap_item->skip_age == 0) {
>>>> +		rmap_item->skip_age = age + inc_skip_age(age);
>>>
>>> Can't you overflow here as well?
>>>
>> Yes, you can. See the above discussion. This skip_age is also an
>> unsigned value.
>
> Dito.
>

I'll make it explicit.

>>
>>>> +		remove_rmap_item_from_tree(rmap_item);
>>>
>>>
>>> Can you enlighten me why that is required?
>>>
>> This is required for age calculation and BUG_ON check in
>> remove_rmap_item_from_tree. If we don't call remove_rmap_item_from_tree,
>> we will hit the BUG_ON for the skipped pages later on.
>
> I see, thanks!