linux-kernel - Re: [PATCH v2 1/4] mm/ksm: add "smart" page scanning mode

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Message-ID: <qvqwbkdp4mlq.fsf@devbig1114.prn1.facebook.com>
Date:   Mon, 25 Sep 2023 20:52:09 -0700
From:   Stefan Roesch <shr@...kernel.io>
To:     David Hildenbrand <david@...hat.com>
Cc:     kernel-team@...com, akpm@...ux-foundation.org, hannes@...xchg.org,
        riel@...riel.com, linux-kernel@...r.kernel.org, linux-mm@...ck.org
Subject: Re: [PATCH v2 1/4] mm/ksm: add "smart" page scanning mode


David Hildenbrand <david@...hat.com> writes:

>> +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;
>
> I *think* of you move that after "oldchecksum", the size of the struct might not
> necessarily increase.
>
> [...]
>
>>   +/*
>> + * Calculate skip age for the ksm page age. The age determines how often
>> + * de-duplicating has already been tried unsuccessfully. If the age is
>> + * smaller, the scanning of this page is skipped for less scans.
>> + *
>> + * @age: rmap_item age of page
>> + */
>> +static unsigned int skip_age(rmap_age_t age)
>> +{
>> +	if (age <= 3)
>> +		return 1;
>> +	if (age <= 5)
>> +		return 2;
>> +	if (age <= 8)
>> +		return 4;
>> +
>> +	return 8;
>> +}
>> +
>> +/*
>> + * Determines if a page should be skipped for the current scan.
>> + *
>> + * @page: page to check
>> + * @rmap_item: associated rmap_item of page
>> + */
>> +static bool should_skip_rmap_item(struct page *page,
>> +				  struct ksm_rmap_item *rmap_item)
>> +{
>> +	rmap_age_t age;
>> +
>> +	if (!ksm_smart_scan)
>> +		return false;
>> +
>> +	/*
>> +	 * Never skip pages that are already KSM; pages cmp_and_merge_page()
>> +	 * will essentially ignore them, but we still have to process them
>> +	 * properly.
>> +	 */
>> +	if (PageKsm(page))
>> +		return false;
>> +
>> +	/*
>> +	 * Smaller ages are not skipped, they need to get a chance to go
>> +	 * through the different phases of the KSM merging.
>> +	 */
>
> Sorry, had to set some time aside to think this through. Wouldn't it be cleaner
> to just not rely on this overflow?
>
> Instead, we could track the page age (which we would freeze at U8_MAX) and
> simply track how much more often we are allowed to skip.
>
> Something like the following (which, I am sure, is completely broken, but should
> express what I have in mind)
>
>
>
> age = rmap_item->age;
> if (age != U8_MAX)
> 	rmap_item->age++;
>
> /*
>  * Smaller ages are not skipped, they need to get a chance to go
>  * through the different phases of the KSM merging.
>  */
> if (age < 3)
> 	return false;
>
> /*
>  * Are we still allowed to skip? If not, then don't skip it
>  * and determine how much more often we are allowed to skip next.
>  */
> if (!rmap_item->remaining_skips) {
> 	rmap_item->remaining_skips = skip_age(age);
> 	return false;
> }
>
> /* Skip this page. */
> rmap_item->remaining_skips--;
> remove_rmap_item_from_tree(rmap_item);
> return true;
>
>
>
> Would that miss anything important? Was the overflow handling (and scanning more
> often one we overflow again IIUC) important?
>

That sounds reasonable. I'll incorporate the two suggestions in the next version.